楼爷八题值poj1743

ゝ一纸荒年。 2021-11-16 14:24 157阅读 0赞

mmp

什么二分  也太难了

先记着，

回来再写

。。。。。

wa了30几发，每天早上醒来都要敲一遍这个题，真是怀疑人生。连续5天，后来发现GCC不能过，C++可以？？？

这，，，，mmp

#include<iostream>
    #include<cstdio>
    using namespace std;
    const int M=3e5+7;
    int x[M],y[M],c[M],sa[M],rk[M],n,m,s[M],a[M],height[M]; 
    void get_sa(){
    	for(int i=1;i<=m;i++) c[i]=0;
    	for(int i=1;i<=n;i++) ++c[x[i]=s[i]];
    	for(int i=2;i<=m;i++) c[i]+=c[i-1];
    	for(int i=n;i;i--) sa[c[x[i]]--]=i;
    	for(int k=1;k<=n;k++){
    		int p=0;
    		for(int i=n-k+1;i<=n;i++)y[++p]=i;
    		for(int i=1;i<=n;i++)if(sa[i]>k) y[++p] = sa[i]-k;
    		for(int i=1;i<=m;i++)c[i]=0;
    		for(int i=1;i<=n;i++)c[x[i]]++;
    		for(int i=2;i<=m;i++)c[i]+=c[i-1];
    		for(int i=n;i;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0;
    		swap(x,y);
    		x[sa[1]]=p=1;
    		for(int i=2;i<=n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p:++p);
    		if(p==n)break;
    		m=p;
    	}
    	for(int i=1;i<=n;i++)rk[sa[i]]=i;
    	int k=0;
    	for(int i=1;i<=n;i++){
    		if(rk[i]==1)continue;
    		if(k)k--;
    		int j=sa[rk[i]-1];
    		while(s[i+k]==s[j+k]&&j+k<=n&&i+k<=n)k++;
    		height[rk[i]]=k; 
    	}
    }
    bool isok(int x){
    	int mn=999999999,mx=-1;
        for(int i=1;i<=n;i++){
            if(height[i]>=x){
                mn=min(sa[i],mn);
                mx=max(sa[i],mx);
                if(mx-mn>x) return 1;
            } else {
                mx=mn=sa[i];
            }
        }
        return 0;
    }
    int main(){
    	while(~scanf("%d",&n)&&n){
    		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    		for(int i=1;i<=n;i++)s[i]=a[i+1]-a[i]+10010;
    		m=20000;
    		get_sa();
    		int l=1,r=n;
    		while(l<=r){
    			int mid=(l+r)>>1;
    			if(isok(mid))l=mid+1;
    			else r=mid-1;
    		}
    		if(l<5)puts("0");
    		else printf("%d\n",l);
    	}
    	return 0;
    }