4698: Sdoi2008 Sandy的卡片
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 140 Solved: 55
[Submit][Status][Discuss]
Description
Sandy和Sue的热衷于收集干脆面中的卡片。然而，Sue收集卡片是因为卡片上漂亮的人物形象，而Sandy则是为了积攒卡片兑换超炫的人物模型。每一张卡片都由一些数字进行标记，第i张卡片的序列长度为Mi，要想兑换人物模型，首先必须要集够N张卡片，对于这N张卡片，如果他们都有一个相同的子串长度为k，则可以兑换一个等级为k的人物模型。相同的定义为：两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。Sandy的卡片数远远小于要求的N，于是Sue决定在Sandy的生日将自己的卡片送给Sandy，在Sue的帮助下，Sandy终于集够了N张卡片，但是，Sandy并不清楚他可以兑换到哪个等级的人物模型，现在，请你帮助Sandy和Sue，看看他们最高能够得到哪个等级的人物模型。
Input
第一行为一个数N，表示可以兑换人物模型最少需要的卡片数，即Sandy现在有的卡片数
第i+1行到第i+N行每行第一个数为第i张卡片序列的长度Mi，之后j+1到j+1+Mi个数，用空格分隔，分别表示序列中
的第j个数
n<=1000,M<=1000,2<=Mi<=101
Output
一个数k，表示可以获得的最高等级。
Sample Input
2
2 1 2
3 4 5 9
2 1 2
3 4 5 9
Sample Output
2
HINT
Source
Solution
又是DCrusher上传的题..做法很普通的一道题..
然而之前自己拿KMP写了一遍..WA...然后又拿后缀数组写了一遍，又WA...然后一直没管..然后这次从新写了一遍，抛去忘关头文件，一遍AC..
就是做差，链接所有串，二分判定一下即可。
后缀数组的写法改动了一下，就当留个模板了....
Code
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
int x=0,f=1; char ch=getchar();
while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
#define MAXN 200000
int N,a[1010][1010],mstr,str;
int S[MAXN],SA[MAXN],rank[MAXN],height[MAXN],st[MAXN],pos[MAXN],t1[MAXN],t2[MAXN];
inline void Sort(int *x,int *y,int *sa,int L,int M)
{
for (int i=0; i<=M; i++) st[i]=0;
for (int i=0; i<L; i++) st[x[y[i]]]++;
for (int i=1; i<=M; i++) st[i]+=st[i-1];
for (int i=L-1; i>=0; i--) sa[--st[x[y[i]]]]=y[i];
}
inline void DA(int *r,int *sa,int L,int M)
{
int *x=t1,*y=t2,*t,i,j,p;
for (int i=0; i<L; i++) x[i]=r[i],y[i]=i;
Sort(x,y,sa,L,M);
for (j=1,p=1; j<L && p<L; j<<=1,M=p-1)
{
for (p=0,i=L-j; i<L; i++) y[p++]=i;
for (i=0; i<L; i++) if (sa[i]>=j) y[p++]=SA[i]-j;
Sort(x,y,sa,L,M);
for (t=x,x=y,y=t,i=1,x[sa[0]]=0,p=1; i<L; i++)
x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+j]==y[sa[i]+j]? p-1:p++;
}
}
inline void Height(int *r,int *sa,int *rank,int *h,int L)
{
h[1]=0;
for (int i=1; i<=L; i++) rank[sa[i]]=i;
for (int i=1,k=0,j; i<=L; h[rank[i++]]=k)
for (k? --k:k=0,j=sa[rank[i]-1]; r[j+k]==r[i+k]; k++);
}
int cnt[MAXN];
inline bool check(int x,int L)
{
int num=0,stack[MAXN],top=0;
for (int i=1; i<=N; i++) cnt[i]=0;
for (int i=2; i<=L; i++)
{
if (height[i]<x)
{
while (top) cnt[stack[top--]]=0;
top=num=0;
}
else
{
if (pos[SA[i-1]] && !cnt[pos[SA[i-1]]])
num++,stack[++top]=pos[SA[i-1]];
cnt[pos[SA[i-1]]]++;
if (pos[SA[i]] && !cnt[pos[SA[i]]])
num++,stack[++top]=pos[SA[i]];
cnt[pos[SA[i]]]++;
}
if (num==N) return 1;
}
return 0;
}
int ls[MAXN],sr,msr,L;
int main()
{
// freopen("card.in","r",stdin);
// freopen("card.out","w",stdout);
N=read();
for (int i=1; i<=N; i++)
{
a[i][0]=read();
for (int j=1; j<=a[i][0]; j++) a[i][j]=read();
}
for (int i=1; i<=N; i++)
{
for (int j=1; j<a[i][0]; j++)
a[i][j]=a[i][j+1]-a[i][j],ls[++sr]=a[i][j];
a[i][0]--;
}
sort(ls+1,ls+1+sr);
msr=sr=unique(ls+1,ls+1+sr)-ls-1;
for (int i=1; i<=N; i++)
{
for (int j=1; j<=a[i][0]; j++)
S[++L]=lower_bound(ls+1,ls+sr+1,a[i][j])-ls,pos[L]=i;
S[++L]=++msr;
}
// for (int i=1; i<=L; i++) printf("%d ",S[i]); puts("");
// for (int i=1; i<=L; i++) printf("%d ",pos[i]); puts("");
DA(S,SA,L+1,msr+1); Height(S,SA,rank,height,L);
// for (int i=1; i<=L; i++) printf("%d ",SA[i]); puts("");
// for (int i=1; i<=L; i++) printf("%d ",pos[SA[i]]); puts("");
// for (int i=2; i<=L; i++) printf("%d ",height[i]); puts("");
int l=0,r=L,ans=0;
while (l<=r)
{
int mid=(l+r)>>1;
if (check(mid,L)) ans=mid,l=mid+1; else r=mid-1;
}
printf("%d
",ans+1);
return 0;
}