P3498 [POI2010]KOR-Beads 题解

· · 题解

0x00 思路

先看题。

Zxl 决定制造一条项链，她买了一串珠子，她有一个机器，能把这条珠子切成很多段，使得每段恰有 k 个珠子 ，如果这条珠子的长度不是 k 的倍数，最后一块长度小于 k 的段就被丢弃了。

Zxl 想知道，选择什么数字 k 可以得到最多的不同的段。注意这里的段是可以反转的，即，子串 1,2,3 和 3,2,1 被认为是一样的。

题面真长，把其简化一下再看。

由于我们希望可以辨别出不同的顺序，所以我们需要使用字符串哈希来做题（若没有哈希冲突那么每一种不同的顺序哈希值都不同）。但是如果是可以反转的话，那么我们就需要将整个字符串反转后的哈希值同样进行计算和存储。

code

#include<map>
#include<cstdio>
#include<string>
#include<cmath>
#include<cstring>
int space[200005],ans[200005],cnt;//原字符串，存答案的，答案个数
unsigned long long Hash[200005],p[200005],Hash2[200005];
const int clac=1504831;
int l,r;
inline void qr(int &ret){int x=0,f=0;char ch;ch=getchar();while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();ret=f?-x:x;return;}
//快读,别翻了

unsigned long long getnum(int l,int r)//原哈希函数
{
    return Hash[r]-Hash[l-1]*p[r-l+1];
}
unsigned long long getnum2(int l,int r)
{
    return Hash2[l]-Hash2[r+1]*p[r-l+1];//由于我的顺序仍然是从1到n，可是我的值是从n开始计算，所以i越小的哈希值越大
}
int main()
{
    int i,n,q,tot,j;
    p[0]=1;
    for(i=1;i<=200000;i++)
        p[i]=p[i-1]*clac;
    qr(n);
    for(i=0;i<n;i++)
        qr(space[i]);
    for(i=1;i<=n;i++)
        Hash[i]=Hash[i-1]*clac+space[i-1];
    for(i=n;i;--i)
        Hash2[i]=Hash2[i+1]*clac+space[i-1];
    int ax=0;
    for(i=1;i<=n;i++)
    {
        int num=0;
        std::map<unsigned long long,bool>mem;//用来记录是否出现过这样的字符串
        for(j=i;j<=n;j+=i)
        {
            unsigned long long sum=getnum(j-i+1,j),sumx=getnum2(j-i+1,j);
            if(!mem.count(sum))
            {
                num++;
                mem[sum]=0;
                mem[sumx]=0;
            }
        }
        if(num>ax)
        {
            cnt=1;
            ans[cnt]=i;
            ax=num;
        }
        else if(num==ax)
            ans[++cnt]=i;
    }
    printf("%d %d\n",ax,cnt);
    for(i=1;i<=cnt;i++)
        printf("%d ",ans[i]);
    return 0;
}

建议继续阅读 SP15569 的题解。