题解 P3498 【[POI2010]KOR-Beads】

· · 题解

题目大意：

给出n个数，可将它们分为若干个串，每个串有k个数（长度不足k则丢弃），求使得不同的串最多的k值及串的个数。串可翻转，即子串1,2,3和3,2,1被认为是一样的。

思路：

本题朴素的思路是枚举k和各个串，比较各个串并记录不同的串，但这样比较和记录的时间复杂度不能做到O(1)，就肯定会超时。但如果比较和记录的时间复杂度是O(1)是不是就不会超时了呢？我们计算一下：

枚举k要O(n)的时间复杂度，而串有\lfloor\dfrac{n}{k}\rfloor个，所以枚举的时间复杂度为

\displaystyle\sum_{k=1}^n\lfloor\dfrac{n}{k}\rfloor

展开后得到

\lfloor\dfrac{n}{1}\rfloor+\lfloor\dfrac{n}{2}\rfloor+...+\lfloor\dfrac{n}{n}\rfloor

近似于

\dfrac{n}{1}+\dfrac{n}{2}+...+\dfrac{n}{n}

把n提出来得到

n(1+\dfrac{1}{2}+...+\dfrac{1}{n})

我们可以发现1+\dfrac{1}{2}+...+\dfrac{1}{n}为调和级数，有

1+\dfrac{1}{2}+...+\dfrac{1}{n}\approx\ln n<\log_2n

又因为我们的比较和记录的时间复杂度是O(1)的，所以总共的时间复杂度便是O(n\log n)。

所以我们便可以想到使用哈希。

与一般的哈希一样，我们先从头弄一个前缀哈希和幂数组，这样若要求i到j位数字的哈希值便可以用hash[j]-hash[i-1]*power[j-i+1]这样来进行计算。但特别的，这题规定串是可以翻转的，所以我们也要从尾弄一个后缀哈希，与前面一样，只不过顺序相反罢了。要求i到j位数字的哈希值可以这样计算：hash[i]-hash[j+1]*power[j-i+1]。这样，查询某个子串便可以这样实现O(1)查询。为了不冲突，此处power每次要乘一个很大的质数才行，这里需要注意。

那么我们的哈希怎么判重呢？我们可以用除余法，若冲突则在下一位保存。如果我们在判重时正反顺序两个都不冲突，我们才认为它是新串，并将正反顺序的哈希值保存下来。

但是我们这里每枚举一次k，都要清空判重数组，这样的时间复杂度是很高的，怎么办呢？我们可以用一个time数组，表示使用当前位的时间，若他的值为规定的时间，就说明它在当前时间被更新过了，就要对当前位的数进行判重，否则说明这个值只是在之前的时间被更新过，与现在无关，就表明当前位无值。这样就不用每次都更新判重数组了。

其他记录答案什么的就是朴素的暴力做法啦~

代码：

#include<cstdio>//以下为了防止不必要的错误，类型我全都开成了unsigned long long
unsigned long long n,m,i,j1,j2,k,max,nans,ans[200005],a[200005],hash[1000007],b[1000007],power[200005],ha1[200005],ha2[200005];//此处的hash为判重数组，b为time数组，power为幂数组，ha1为前缀哈希，ha2为后缀哈希
unsigned long long ha(unsigned long long x)//判重
{
    unsigned long long y=x%1000007;
    if (b[y]==m&&hash[y]!=x)
    {
        y++;
        if (y==n/m)
        y=0;
    }
    return y;
}
int main()
{
    scanf("%d",&n);
    power[0]=1;
    for (m=1;m<=n;m++)
    scanf("%d",&a[m]),power[m]=power[m-1]*19260817,ha1[m]=ha1[m-1]*19260817+a[m];//读入并预处理幂数组与前缀哈希
    for (m=n;m;m--)
    ha2[m]=ha2[m+1]*19260817+a[m];//预处理后缀哈希
    for (m=1;m<=n;m++)//枚举题目中的k
    {
        k=0;//k为不同串的个数
        for (i=m+1;i<=n+1;i+=m)
        {
            j1=ha(ha1[i-1]-ha1[i-m-1]*power[m]);
            if (hash[j1]==ha1[i-1]-ha1[i-m-1]*power[m])//判断正序是否重复
            continue;
            j2=ha(ha2[i-m]-ha2[i]*power[m]);
            if (hash[j2]==ha2[i-m]-ha2[i]*power[m])//判断反序是否重复
            continue;
            b[j1]=b[j2]=m,hash[j1]=ha1[i-1]-ha1[i-m-1]*power[m],hash[j2]=ha2[i-m]-ha2[i]*power[m],k++;//记录时间戳，保存正反顺序两个串
        }
        //以下为记录答案
        if (k>max)
        max=k,nans=1,ans[1]=m;
        else
        if (k==max)
        nans++,ans[nans]=m;
    }
    printf("%lld %lld\n",max,nans);
    for (m=1;m<=nans;m++)
    printf("%lld ",ans[m]);
    return 0;
}