題目描述

Sandy和Sue的熱衷于收集干脆面中的卡片。

然而，Sue收集卡片是因為卡片上漂亮的人物形象，而Sandy則是為了積攢卡片兌換超炫的人物模型。

每一張卡片都由一些數(shù)字進(jìn)行標(biāo)記，第i張卡片的序列長度為Mi，要想兌換人物模型，首先必須要集夠N張卡片，對于這N張卡片，如果他們都有一個相同的子串長度為k，則可以兌換一個等級為k的人物模型。相同的定義為：兩個子串長度相同且一個串的全部元素加上一個數(shù)就會變成另一個串。

Sandy的卡片數(shù)遠(yuǎn)遠(yuǎn)小于要求的N，于是Sue決定在Sandy的生日將自己的卡片送給Sandy，在Sue的幫助下，Sandy終于集夠了N張卡片，但是，Sandy并不清楚他可以兌換到哪個等級的人物模型，現(xiàn)在，請你幫助Sandy和Sue，看看他們最高能夠得到哪個等級的人物模型。

輸入輸出格式

輸入格式：

第一行為一個數(shù)N，表示可以兌換人物模型最少需要的卡片數(shù)，即Sandy現(xiàn)在有的卡片數(shù)

第i+1行到第i+N行每行第一個數(shù)為第i張卡片序列的長度Mi，之后j+1到j(luò)+1+Mi個數(shù)，用空格分隔，分別表示序列中的第j個數(shù)

輸出格式：

一個數(shù)k，表示可以獲得的最高等級。

輸入輸出樣例

輸入樣例#1： 復(fù)制 2 2 1 2 3 4 5 9 輸出樣例#1： 復(fù)制 2

說明

數(shù)據(jù)范圍：

30%的數(shù)據(jù)保證n<=50

100%的數(shù)據(jù)保證n<=1000

因為是“相似”，所以把n個字符串差分

用不同且未出現(xiàn)的分隔符連起來

然后求后綴數(shù)組和LCP

二分答案k

把連續(xù)的h值不小于k的分為一組，如果一組內(nèi)集齊了n個字符串的后綴

那么就可以構(gòu)成長度為k的相似子串

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 int s[2000001],c[2000001],SA[2000001],h[2000001],n,m,x[2000001],y[2000001],rank[2000001],ans,tot,len[1501],cnt; 8 int bel[2000001],mx=4000,a[2001][2001],top,st[2000001]; 9 bool vis[1501]; 10 void radix_sort() 11 {int i; 12 for (i=0;i<m;i++) 13 c[i]=0; 14 for (i=0;i<n;i++) 15 c[x[y[i]]]++; 16 for (i=1;i<m;i++) 17 c[i]+=c[i-1]; 18 for (i=n-1;i>=0;i--) 19 SA[--c[x[y[i]]]]=y[i]; 20 } 21 void build_SA() 22 {int i,j,k,p; 23 for (i=0;i<n;i++) 24 x[i]=s[i],y[i]=i; 25 m=1000000; 26 radix_sort(); 27 for (k=1;k<=n;k<<=1) 28 { 29 p=0; 30 for (i=n-k;i<n;i++) 31 y[p++]=i; 32 for (i=0;i<n;i++) 33 if (SA[i]>=k) y[p++]=SA[i]-k; 34 radix_sort(); 35 p=1;swap(x,y); 36 x[SA[0]]=0; 37 for (i=1;i<n;i++) 38 x[SA[i]]=((y[SA[i]]==y[SA[i-1]])&&((SA[i]+k<n?y[SA[i]+k]:-1)==(SA[i-1]+k<n?y[SA[i-1]+k]:-1)))?p-1:p++; 39 if (p>=n) break; 40 m=p; 41 } 42 for (i=0;i<n;i++) 43 rank[SA[i]]=i; 44 int L=0; 45 for (i=0;i<n;i++) 46 if (rank[i]>0) 47 { 48 if (L>0) L--; 49 j=SA[rank[i]-1]; 50 while (i+L<n&&j+L<n&&(s[j+L]==s[i+L])) L++; 51 h[rank[i]]=L; 52 } 53 } 54 bool check(int mid) 55 { 56 int num=0; 57 for(int i=0;i<=n;i++) 58 { 59 if(h[i]<mid) 60 { 61 num=0; 62 while(top) vis[st[top--]]=0; 63 } 64 if(!vis[bel[SA[i]]]) 65 { 66 vis[bel[SA[i]]]=1; 67 num++; 68 st[++top]=bel[SA[i]]; 69 } 70 if(num==tot)return 1; 71 } 72 return 0; 73 } 74 int main() 75 {int l,r,i,now,last,j; 76 cin>>tot;r=2e9; 77 for (i=1;i<=tot;i++) 78 { 79 scanf("%d",&len[i]); 80 r=min(r,len[i]); 81 for (j=1;j<=len[i];j++) 82 { 83 scanf("%d",&a[i][j]); 84 } 85 } 86 for (i=1;i<=tot;i++) 87 { 88 for (j=2;j<=len[i];j++) 89 { 90 s[cnt]=a[i][j]-a[i][j-1]+2000; 91 bel[cnt]=i; 92 cnt++; 93 } 94 s[cnt++]=++mx; 95 } 96 n=cnt; 97 build_SA(); 98 l=1;r--; 99 ans=0; 100 while (l<=r) 101 { 102 int mid=(l+r)/2; 103 if (check(mid)) ans=mid,l=mid+1; 104 else r=mid-1; 105 } 106 cout<<ans+1; 107 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Y-E-T-I/p/8480466.html

總結(jié)

以上是生活随笔為你收集整理的[SDOI2008]Sandy的卡片的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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