BZOJ-4698: Sdoi2008 Sandy的卡片

Description

每一张卡片都由一些数字进行标记，第i张卡片的序列长度为Mi，要想兑换人物模型，首先必须要集够N张卡片，对于这N张卡片，如果他们都有一个相同的子串长度为k，则可以兑换一个等级为k的人物模型。相同的定义为：两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。Sandy的卡片数远远小于要求的N，于是Sue决定在Sandy的生日将自己的卡片送给Sandy，在Sue的帮助下，Sandy终于集够了N张卡片，但是，Sandy并不清楚他可以兑换到哪个等级的人物模型，现在，请你帮助Sandy和Sue，看看他们最高能够得到哪个等级的人物模型。n<=1000

经典套路，差分之后二分+hash。

#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
int n,map[1010][110],ans;
set<ull>s;
set<ull>::iterator it;
ull Pow(ull x,int y)
{
    ull re=1;
    while(y)
    {
        if(y&1) re=re*x;
        x=x*x; y>>=1;
    }
    return re;
}
bool check(int x)
{
    ull has,po; static ull z[200]; int top=0,now;
    for(int i=1;i<=n;++i)
    {
        has=0; s.clear();
        for(int j=2;j<=x+1;++j) has=has*233+map[i][j];
        s.insert(has); po=Pow(233,x-1);
        for(int j=x+2;j<=map[i][0];++j)
        {
            has-=po*map[i][j-x];
            has=has*233+map[i][j];
            s.insert(has);
        }
        if(i==1) for(it=s.begin();it!=s.end();it++) z[++top]=*it;
        else
        {
            now=1;
            while(now<=top)
            {
                if(s.find(z[now])!=s.end()) now++;
                else swap(z[now],z[top]),top--;
            }
        }
        if(top==0) return false;
    }
    return true;
}
int main()
{
    scanf("%d",&n); int l=1,r=0x3f3f3f3f,mid;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&map[i][0]); r=min(r,map[i][0]);
        for(int j=1;j<=map[i][0];++j)
            scanf("%d",&map[i][j]);
        for(int j=map[i][0];j>1;--j)
            map[i][j]-=map[i][j-1];
    }
    while(l<r)
    {
        mid=(l+r)>>1;
        if(check(mid)) l=mid+1;
        else r=mid;
    }
    ans=max(1,l);
    printf("%d",ans);
    return 0;
}