WA#5
查看原帖
WA#5
544780
dodo487楼主2023/4/18 10:43
#include<bits/stdc++.h>
using namespace std;
int a[102000],aa[102000];
int sa[102000],x[102000],y[102000],c[301000],rk[102000],height[102000];
int id[102000];
int n,m;
int cntt=2000;
void getsa(){
	for(int i=1;i<=n;i++) c[x[i]=a[i]]++;
	for(int i=2;i<301000;i++) c[i]+=c[i-1];
	for(int i=n;i>=1;i--) sa[c[x[i]]--]=i;
	
	for(int k=1;k<=n;k<<=1){
		int num=0;
		for(int i=n-k+1;i<=n;i++) y[++num]=i;
		for(int i=1;i<=n;i++){
			if(sa[i]>k){
				y[++num]=sa[i]-k;
			}
		}
		
		for(int i=1;i<301000;i++) c[i]=0;
		for(int i=1;i<=n;i++) c[x[i]]++;
		for(int i=2;i<301000;i++) c[i]+=c[i-1];
		for(int i=n;i>=1;i--){
			sa[c[x[y[i]]]--]=y[i],y[i]=0;
		}
		
		swap(x,y);
		
		num=1;
		x[sa[1]]=1;
		for(int i=2;i<=n;i++){
			if(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) x[sa[i]]=num;
			else x[sa[i]]=++num;
		}
		if(num==n) break;
		m=num;
	}
	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(i+k<=n&&j+k<=n&&a[i+k]==a[j+k]) k++;
		height[rk[i]]=k;
	}
}
bool vis[102000];
int T;
stack<int> st;
bool check(int mid){
	while(st.size()) vis[st.top()]=0,st.pop();
	for(int i=1;i<=n;i++){
		if(height[i]<mid) while(st.size())vis[st.top()]=0,st.pop();
		if(vis[id[sa[i]]]) continue;
		st.push(id[sa[i]]);
		vis[st.top()]=1;
		if(st.size()>=T) return 1;
	}
	return 0;
}
signed main(){
	scanf("%d",&T);
	int minn=0x7fffffff;
	int maxx=0;
	for(int i=1;i<=T;i++){
		int sz;
		scanf("%d",&sz);
		for(int j=1;j<=sz;j++){
			scanf("%d",&aa[j]);
			a[++n]=aa[j]-aa[j-1];
			minn=min(minn,a[n]);
			id[n]=i;
		}
		a[++n]=i+cntt;
	}
	for(int i=1;i<=n;i++) a[i]=a[i]-minn+1;
	for(int i=1;i<=n;i++) m=max(m,a[i]);
	getsa();
	int l=0,r=n,ans=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)) l=mid+1,ans=mid;
		else r=mid-1;
	}
	cout<<ans+1<<endl;
}
2023/4/18 10:43
加载中...