> #include<cstdio>
> #include<cstring>
> using namespace std;
> typedef int aa[30000];
> aa a,ws,wb,wa,sa,ra,wv,Height,h;
> int n;
> void init()
> {
> 	memset(sa,0,sizeof(sa));
> 	memset(ra,0,sizeof(ra));
> 	for (int i=0;i<n;++i)
> 		scanf("%d",&a[i]);
> 	for (int i=0;i<n-1;++i) a[i]=a[i+1]-a[i]+100;
> 	a[n-1]=0;
> }
> bool cmp(int *r,int i, int j, int k)
> {
> 	return r[i]==r[j]&&r[i+k]==r[j+k];
> }
> void da(int *r,int *sa,int n,int m)
> {
> 	int i,j,p,*x=wa,*y=wb,*t;
> 	for (i=0;i<m;++i) ws[i]=0;
> 	for (i=0;i<n;++i) ws[x[i]=r[i]]++;
> 	for (i=1;i<m;++i) ws[i]+=ws[i-1];
> 	for (i=n-1;i>=0;--i) sa[--ws[x[i]]]=i;
> 	for (j=1,p=1;p<n;j=j<<1,m=p)
> 	{
> 		for (p=0,i=n-j;i<n;++i) y[p++]=i;
> 		for (i=0;i<n;++i) if (sa[i]>=j) y[p++]=sa[i]-j;
> 		for (i=0;i<m;++i) ws[i]=0;
> 		for (i=0;i<n;++i) wv[i]=x[y[i]];
> 		for (i=0;i<n;++i) ws[wv[i]]++;
> 		for (i=1;i<m;++i) ws[i]+=ws[i-1];
> 		for (i=n-1;i>=0;--i) sa[--ws[wv[i]]]=y[i];
> 		for (t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;++i)
> 			x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
> 	}
> }
> void calHeight(int *r,int n)
> {
> 	int i=0,j,p=0;
> 	for (i=0;i<n;++i) ra[sa[i]]=i;
> 	for (i=0;i<n;Height[ra[i++]]=p)
> 		for (p?p--:0,j=sa[ra[i]-1];r[j+p]==r[i+p];p++);
> 	memcpy(h,Height,sizeof(Height));
> }
> void prepare(int x)
> {
> 	memcpy(Height,h,sizeof(h));
> 	for (int i=0;i<n;++i)
> 	{
> 		Height[i]-=x-1;
> 		if (Height[i]<0) Height[i]=0;
> 	}
> }
> void expand(int &min,int &max,int x)
> {
> 	if (x>max) max=x;
> 	if (x<min) min=x;
> }
> bool check(int x)
> {
> 	prepare(x);
> 	int min=1000000,max=0;
> 	for (int i=0;i<n;++i)
> 	{
> 		if (Height[i]==0) 
> 		{  
> 			if (max-min>x) return 1;
> 			min=1000000; max=0;
> 			continue;
> 		}
> 		expand(min,max,sa[i]);
> 		expand(min,max,sa[i-1]);
> 	}
> 	if (max-min>x) return 1;
> 	return 0;
> }
> void solve()
> {
> 	da(a,sa,n,300);
> 	calHeight(a,n);
> 	int l=0,r=n;
> 	while (l+1<r)
> 	{
> 		int mid=(l+r)/2;
> 		if (check(mid)) l=mid;
> 		else r=mid;
> 	}
> 	if (l+1<5) printf("0\n");
> 	else printf("%d\n",l+1);
> }
> int main()
> {
> 	scanf("%d",&n);
> 	while (n!=0)
> 	{
> 		init();	
> 		if (n==1) printf("0\n"); //****************
> 		else solve();
> 		scanf("%d",&n);
> 	}
> 	return 0;
> }

• Re:巨坑！大家亲注意n=1时的情况。。。。否则无限RE (7) moya_hy 2013-09-01 19:11:40
  • Re:巨坑！大家亲注意n=1时的情况。。。。否则无限RE (4) liucy1998 2017-10-06 15:54:36