題目大意：給你一個字符串，求所有子串的所有優秀拆分總和，優秀的拆分被定義為一個字符串可以被拆分成4個子串，形如$AABB$，其中$AA$相同，$BB$相同，$AB$也可以相同

作為一道國賽題，95分竟然就這么給我們了！只是一個$NOIP$難度的哈希套$DP$啊......

95分就是從后往前找，統計$AA$串，每次統計一下從這個位置開始的所有子串 和 緊隨其后的等長串 相同的個數$sum$

$hash(i,i+j-1)==hash(i+j,i+2*j-1) sum[i]++$

然后再統計$BB$串，就是加上在這兩個串之后的位置的$sum$值，這樣就統計出了合法拆分數

$dp[i]+=sum[i+2*j]$

95分就這樣到手啦，竟然連自然溢出hash都不卡

1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define ll long long 6 #define ull unsigned long long 7 #define N 2050 8 #define seed 233 9 #define idx(x) (x-'a'+1) 10 using namespace std; 11 //re 12 int T,len; 13 char str[N]; 14 int dp[N],sum[N]; 15 ull hsh[N],sp[N]; 16 ull ghsh(int x,int y) {return hsh[y]-hsh[x-1]*sp[y-x+1];} 17 void clr() 18 { 19 memset(dp,0,sizeof(dp)); 20 memset(sp,0,sizeof(sp)); 21 memset(sum,0,sizeof(sum)); 22 memset(hsh,0,sizeof(hsh)); 23 } 24 int main() 25 { 26 scanf("%d",&T); 27 while(T--) 28 { 29 clr(); 30 scanf("%s",str+1); 31 len=strlen(str+1); 32 sp[0]=1; 33 for(int i=1;i<=len;i++) 34 hsh[i]=hsh[i-1]*seed+idx(str[i]), 35 sp[i]=sp[i-1]*seed; 36 for(int i=len-1;i>=1;i--) 37 { 38 for(int j=1;i+2*j-1<=len;j++) 39 { 40 if(ghsh(i,i+j-1)==ghsh(i+j,i+2*j-1)){ 41 dp[i]++; 42 sum[i]+=dp[i+2*j]; 43 } 44 } 45 } 46 int ans=0; 47 for(int i=1;i<=len;i++) 48 ans+=sum[i]; 49 printf("%d\n",ans); 50 } 51 return 0; 52 }

接下來才是本題的重點！$NOI$豈是你想$AK$就$AK$的！出題人可能是想針對某位巨佬

不看題解這個正解思路真是很難想到......

思路大概是這樣的，其實我們每次只需要統計$AA$串的數量就行了，因為$AABB$串的數量等于，在$i-1$位結束的$AA$串的數量乘以在第$i$位開始的$AA$串的數量，用公式表示就是

接下來就是統計$st$和$ed$了，感覺正解的思路很神

先用后綴數組+$ST$表處理出任意兩個位置，作為后綴串開頭的$LCP$以及作為前綴串末尾的$LCS$，求$LCS$可以把串反著讀再去套$SA$

每次選取一個$A$串的長度$len$，再在原串每隔$len$的位置設一個關鍵點

然后會發現一個神奇的性質，任意一個長度為$2*len$的串必然經過且僅經過2個關鍵點！

接下來統計經過所有長度為$2*len$所有$AA$串，比如選定兩個關鍵點$a,b$，且$a+len=b$

如果把$a$的和b$相同的前綴和后綴拼在一起，且拼完之后長度>=len，說明存在至少一個$AA$串

可以把$AA$串想象成一個塊，在兩個關鍵點上移動，塊的左端點不能大于$a$，塊的右端點不能小于$b$，塊不能移動到上一個或者下一個關鍵點的位置，塊內必須是$AA$串，這樣，塊所有能移動的位置-塊的長度$len$，就是經過$ab$兩個關鍵點的所有$AA$串數

時間變成，$logn$是調和級數的近似值

細節比較多需要仔細思考

1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define ll long long 6 #define N 30100 7 #define seed 233 8 #define idx(x) (x-'a'+1) 9 using namespace std; 10 //re 11 int T,len; 12 int lg[N]; 13 ll st[N],ed[N],S[N],E[N]; 14 struct suffix{ 15 char str[N]; 16 int sa[N],tr[N],rk[N],hs[N],h[N],f[N][15],len; 17 bool check(int k,int x,int y){ 18 if(x+k>len||y+k>len) return 0; 19 else return (rk[x]==rk[y]&&rk[x+k]==rk[y+k])?1:0; 20 } 21 void get_suffix() 22 { 23 int cnt=0,i;len=strlen(str+1); 24 for(i=1;i<=len;i++) hs[str[i]]++; 25 for(i=1;i<=127;i++) if(hs[i]) tr[i]=++cnt; 26 for(i=1;i<=127;i++) hs[i]+=hs[i-1]; 27 for(i=1;i<=len;i++) rk[i]=tr[str[i]],sa[hs[str[i]]--]=i; 28 for(int k=1;cnt<len;k<<=1) 29 { 30 for(i=1;i<=cnt;i++) hs[i]=0; 31 for(i=1;i<=len;i++) hs[rk[i]]++; 32 for(i=1;i<=cnt;i++) hs[i]+=hs[i-1]; 33 for(i=len;i>=1;i--) if(sa[i]>k) tr[sa[i]-k]=hs[rk[sa[i]-k]]--; 34 for(i=1;i<=k;i++) tr[len-i+1]=hs[rk[len-i+1]]--; 35 for(i=1;i<=len;i++) sa[tr[i]]=i; 36 for(i=1,cnt=0;i<=len;i++) tr[sa[i]]=check(k,sa[i],sa[i-1])?cnt:++cnt; 37 for(i=1;i<=len;i++) rk[i]=tr[i]; 38 } 39 for(i=1;i<=len;i++) 40 { 41 if(rk[i]==1) continue; 42 for(int j=max(1,h[rk[i-1]]-1);;j++) 43 if(str[i+j-1]==str[sa[rk[i]-1]+j-1]) h[rk[i]]=j; 44 else break; 45 } 46 } 47 void get_ST() 48 { 49 for(int i=1;i<=len;i++) 50 f[i][0]=h[i]; 51 for(int k=1;(1<<k)<=len;k++) 52 for(int i=1;i+(1<<k)-1<=len;i++) 53 f[i][k]=min(f[i][k-1],f[i+(1<<(k-1))][k-1]); 54 } 55 int query(int x,int y) 56 {int L=y-x+1; 57 return min(f[x][lg[L]],f[y-(1<<lg[L])+1][lg[L]]);} 58 }p,s; 59 void clr() 60 { 61 memset(S,0,sizeof(S)),memset(st,0,sizeof(st)); 62 memset(E,0,sizeof(E)),memset(ed,0,sizeof(ed)); 63 memset(&p,0,sizeof(p)),memset(&s,0,sizeof(s)); 64 } 65 int main() 66 { 67 scanf("%d",&T); 68 for(int i=2;i<=30010;i++) 69 lg[i]=lg[i>>1]+1; 70 while(T--) 71 { 72 clr(); 73 scanf("%s",s.str+1); 74 int len=strlen(s.str+1); 75 for(int i=1;i<=len;i++) 76 p.str[i]=s.str[len-i+1]; 77 s.get_suffix(); 78 s.get_ST(); 79 p.get_suffix(); 80 p.get_ST(); 81 int sx,sy,px,py,ss,sp,l,r; 82 for(int i=1;i<=len;i++) 83 { 84 for(int j=i+1;j<=len;j+=i) 85 { 86 sx=s.rk[j-i+1],sy=s.rk[j+1]; 87 if(sx>sy) swap(sx,sy); 88 px=p.rk[len-(j-i)+1],py=p.rk[len-j+1]; 89 if(px>py) swap(px,py); 90 ss=s.query(sx+1,sy); 91 sp=p.query(px+1,py); 92 if(ss+sp<i||sp==0) continue; 93 l=max(j-i-i+1,j-i-sp+1); 94 r=min(j+i-1,j+ss); 95 S[l]++,S[r-2*i+2]--; 96 E[l+2*i-1]++,E[r+1]--; 97 } 98 } 99 for(int i=1;i<=len;i++) 100 st[i]=st[i-1]+S[i],ed[i]=ed[i-1]+E[i]; 101 ll ans=0; 102 for(int i=2;i<=len;i++) 103 ans+=ed[i-1]*st[i]; 104 printf("%lld\n",ans); 105 } 106 return 0; 107 }

?

轉載于:https://www.cnblogs.com/guapisolo/p/9707026.html

總結

以上是生活随笔為你收集整理的NOI 2016 优秀的拆分 (后缀数组+差分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。