題解: 裸后綴數(shù)組+二分答案

/**************************************************************Problem: 4698User: c20161007Language: C++Result: AcceptedTime:272 msMemory:87240 kb ****************************************************************/#include <bits/stdc++.h> const int MAXN=2e6+10; using namespace std; int length[1005],vis[MAXN],s[1005]; int n,maxn=101,len,minn=1000000; int str[MAXN]; int txt[MAXN],td[MAXN],rank1[MAXN],rank2[MAXN],sa[MAXN],t1[MAXN],t2[MAXN]; bool cmp(int f[],int w,int e,int k){return f[w]==f[e]&&f[w+k]==f[e+k];} void Sa(){int m=4004;int *td=t1;int *rank1=t2;for(int i=0;i<m;i++)txt[i]=0;for(int i=0;i<len;i++)rank1[i]=str[i],txt[str[i]]++;for(int i=1;i<m;i++)txt[i]+=txt[i-1];for(int i=len-1;i>=0;i--)sa[--txt[str[i]]]=i;for(int k=1;k<=len;k*=2){int p=0;for(int i=len-k;i<len;i++)td[p++]=i;for(int i=0;i<len;i++)if(sa[i]>=k)td[p++]=sa[i]-k;for(int i=0;i<m;i++)txt[i]=0;for(int i=0;i<len;i++)txt[rank1[i]]++;for(int i=1;i<m;i++)txt[i]+=txt[i-1];for(int i=len-1;i>=0;i--)sa[--txt[rank1[td[i]]]]=td[i];swap(rank1,td);rank1[sa[0]]=0;p=1;for(int i=1;i<len;i++)rank1[sa[i]]=cmp(td,sa[i],sa[i-1],k)?p-1:p++;if(p==len)return ;m=p;} } int h[MAXN],H[MAXN]; void hh(){for(int i=0;i<len;i++)rank2[sa[i]]=i;memset(H,0,sizeof(H));for(int i=0;i<len;i++){if(rank2[i]==0)continue;int t=sa[rank2[i]-1];int w=i;int k;if(i==0||H[i-1]<=1)k=0;else k=H[i-1]-1,w+=k,t+=k;while(t<len&&w<len){if(str[t]==str[w])k++;else break;t++;w++;}H[i]=k;h[rank2[i]]=k;} } void inte(){scanf("%d",&n);len=0;int csh=0;for(int i=1;i<=n;i++){scanf("%d",&length[i]);minn=min(minn,length[i]);for(int j=0;j<length[i];j++)scanf("%d",&s[j]);vis[len]=i;str[len++]=++csh;for(int j=1;j<length[i];j++)vis[len]=i,str[len++]=s[j]-s[j-1]+3000;vis[len]=0;str[len++]=++csh;}// for(int i=0;i<len;i++)cout<<str[i]<<" ";//cout<<endl;// for(int i=1;i<len;i++)cout<<sa[i]<<" ";// cout<<endl; } bool tag[1005]; bool check(int t){int cnt=0;memset(tag,0,sizeof(tag));for(int i=1;i<len;i++){ // if(!vis[sa[i]])continue;if(!vis[sa[i]]||h[i]<t){cnt=0;memset(tag,0,sizeof(tag));}else{// cout<<"sb"<<endl;// cout<<vis[sa[i-1]]<<" "<<vis[sa[i]]<<endl;if(!tag[vis[sa[i-1]]])cnt++,tag[vis[sa[i-1]]]=1;if(!tag[vis[sa[i]]])cnt++,tag[vis[sa[i]]]=1;if(cnt>=n)break;}}if(cnt>=n)return true;return false; } void slove(){inte();Sa();hh();// for(int i=0;i<len;i++)cout<<sa[i]<<" ";// cout<<endl;// for(int i=1;i<len;i++)cout<<h[i]<<" ";// cout<<endl;int l=1,r=minn;int ans=0;while(l<=r){int mid=(l+r)>>1; // cout<<mid<<"===="<<endl;if(check(mid))ans=mid,l=mid+1;else r=mid-1;}printf("%d\n",ans+1); } int main(){// scanf("%d",&n);slove();return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/wang9897/p/9174550.html

與50位技術(shù)專(zhuān)家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的BZOJ4698: Sdoi2008 Sandy的卡片的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。