蒟蒻爆0求调(
查看原帖
蒟蒻爆0求调(
556740
hzx360楼主2023/12/18 17:48
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+100;
int s[N*1000];
int T,n,m,K,num,cnt[N*1000],sa[N*1000],rk[N*1000],ht[N*1000],pos[N*1000],x[N*1000],bb[N*1000];
void get_sa(){
	m=4000;
	for(int i=1;i<=m;i++) cnt[i]=0;
	for(int i=1;i<=n;i++) cnt[x[i]=s[i]]++;
	for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;i--) sa[cnt[x[i]]--]=i;
	
	for(int k=1;k<=n;k<<=1){
		num=0;
		for(int i=n-k+1;i<=n;i++) pos[++num]=i;
		for(int i=1;i<=n;i++) if(sa[i]>k) pos[++num]=sa[i]-k;
		for(int i=1;i<=m;i++) cnt[i]=0;
		for(int i=1;i<=n;i++) cnt[x[i]]++;
		for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;i--) sa[cnt[x[pos[i]]]--]=pos[i],bb[i]=x[i];
		x[sa[1]]=1,num=1;
		for(int i=2;i<=n;i++) x[sa[i]]=(bb[sa[i]]==bb[sa[i-1]] && bb[sa[i]+k]==bb[sa[i-1]+k])?num:++num;
		m=num;
		if(n==m) break;
	}
	return;
}
void get_height(){
	int k=0;
	for(int i=1;i<=n;i++) rk[sa[i]]=i;
	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] and i+k<=n and j+k<=n) ++k;
		ht[rk[i]]=k;
	}
}
deque<int>q;
bool check(int mid){
	for(int i=1;i<=n;i++){
		while(!q.empty() and i-q.front()>=T) q.pop_front();
		while(!q.empty() and ht[i]<=ht[q.back()]) q.pop_back();
		q.push_back(i);
		if(i>=T){
			if(q.front()==i-T+1){
				q.pop_front();
				if(ht[q.front()]>=mid){
					q.clear();;
					return 1;
				}
			}
			else{
				if(ht[q.front()]>=mid){
					q.clear();
					return 1;
				}
			}
		}
	}
	return 0;
}
signed main(){
	cin>>T;
	int ans=1000000;
	for(int i=1;i<=T;i++){
		int nn;
		scanf("%lld",&nn);
		ans=min(ans,nn);
		int last=-1;
		for(int i=1;i<=nn;i++){
			int X;scanf("%lld",&X);
			if(last==-1) last=X;
			s[++n]=X-last;
			last=X;
		}
		s[++n]=2000;
	}
	if(T==1){
		cout<<ans;
		return 0;
	}
	for(int i=1;i<=n;i++) s[i]+=2000;//防止出现负数 
	get_sa(),get_height();
	int l=1,r=ans; ans=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)) l=mid+1,ans=mid;
		else r=mid-1;
	}
	cout<<ans;
	return 0;
}
2023/12/18 17:48
加载中...