UOJ #219 BZOJ 4650 luogu P1117 [NOI2016]優(yōu)秀的拆分 (后綴數(shù)組、ST表)

連NOI Day1T1都不會(huì)做。。。看了題解都寫(xiě)不出來(lái)還要抄Claris的代碼。。

題目鏈接: (luogu)https://www.luogu.org/problemnew/show/P1117

(bzoj)https://www.lydsy.com/JudgeOnline/problem.php?id=4650

(uoj)http://uoj.ac/problem/219

題解:

\(f[i]\)表示以\(i\)結(jié)束的\(AA\)型子串個(gè)數(shù)，\(g[i]\)表示以\(i\)開(kāi)始的\(AA\)型子串個(gè)數(shù)

怎么求\(f,g\)?

打破思維定勢(shì)，誰(shuí)說(shuō)必須要一個(gè)一個(gè)求呢

分長(zhǎng)度來(lái)求

枚舉長(zhǎng)度\(L\), 處理所有長(zhǎng)度為\(2L\)的\(AA\)型子串對(duì)\(f\)和\(g\)的貢獻(xiàn)

如果每隔\(L\)的長(zhǎng)度放一個(gè)打點(diǎn)計(jì)時(shí)器，呸，關(guān)鍵點(diǎn)

那么任何\(AA\)型子串都會(huì)經(jīng)過(guò)兩個(gè)相鄰關(guān)鍵點(diǎn)

首先肯定要滿(mǎn)足這兩個(gè)關(guān)鍵位置上的字符一樣

在這個(gè)基礎(chǔ)上求出往前往后最多多少個(gè)一樣的

這個(gè)就轉(zhuǎn)化成了LCP和LCS問(wèn)題，并且兩個(gè)相鄰關(guān)鍵點(diǎn)對(duì)\(f,g\)數(shù)組的影響是區(qū)間+1，使用差分前綴和解決

然后推一推就行了，注意+1-1不要推錯(cuò)

時(shí)間復(fù)雜度為調(diào)和級(jí)數(shù)，\(O(n\log n)\)

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define llong long long using namespace std;const int N = 1<<15; const int LGN = 15; const int S = 26; int log2[N+3]; struct SparseTable {int n;int str[N+3];int rk[N+3];int tmp[N+3];int height[N+3];int h[N+3];int sa[N+3];int wb[N+3];int mini[N+3][LGN+3];void get_sa(){int *x = rk,*y = tmp;for(int i=0; i<=S; i++) wb[i] = 0;for(int i=1; i<=n; i++) wb[x[i]=str[i]]++;for(int i=1; i<=S; i++) wb[i] += wb[i-1];for(int i=n; i>=1; i--) sa[wb[x[i]]--] = i;int s = S,p = 0;for(int j=1; p<n; j<<=1){p = 0;for(int i=n-j+1; i<=n; i++) y[++p] = i;for(int i=1; i<=n; i++) if(sa[i]>j) y[++p] = sa[i]-j;for(int i=1; i<=s; i++) wb[i] = 0;for(int i=1; i<=n; i++) wb[x[y[i]]]++;for(int i=1; i<=s; i++) wb[i] += wb[i-1];for(int i=n; i>=1; i--) sa[wb[x[y[i]]]--] = y[i];swap(x,y);p = 1; x[sa[1]] = 1;for(int i=2; i<=n; i++) x[sa[i]] = (y[sa[i]]==y[sa[i-1]] && y[sa[i]+j]==y[sa[i-1]+j]) ? p : ++p;s = p;}for(int i=1; i<=n; i++) rk[sa[i]] = i;for(int i=1; i<=n; i++){h[i] = h[i-1]==0 ? 0 : h[i-1]-1;while(i+h[i]<=n && sa[rk[i-1]]+h[i]<=n && str[i+h[i]]==str[sa[rk[i]-1]+h[i]]){h[i]++;}}for(int i=1; i<=n; i++) height[i] = h[sa[i]];for(int i=1; i<=n; i++) mini[i][0] = height[i];for(int j=1; j<=LGN; j++){for(int i=1; i+(1<<j)-1<=n; i++){mini[i][j] = min(mini[i][j-1],mini[i+(1<<j-1)][j-1]);}}}int querymin(int lb,int rb){int g = log2[rb-lb+1];return min(mini[lb][g],mini[rb-(1<<g)+1][g]);}int LCP(int x,int y){if(x==y) return n-x+1;if(rk[x]>rk[y]) swap(x,y);return querymin(rk[x]+1,rk[y]);}void clear(){for(int i=1; i<=n; i++) str[i] = rk[i] = tmp[i] = height[i] = h[i] = sa[i] = wb[i] = 0;for(int i=1; i<=n; i++){for(int j=0; j<=LGN; j++){mini[i][j] = 0;}}} } s1,s2; llong f[N+3]; llong g[N+3]; char a[N+3]; int n;int LCP(int x,int y) {return s1.LCP(x,y);} int LCS(int x,int y) {return s2.LCP(n+1-x,n+1-y);}void preprocess() {log2[1] = 0; for(int i=2; i<=N; i++) log2[i] = log2[i>>1]+1; }void clear() {s1.clear(); s2.clear();for(int i=0; i<=n+1; i++) a[i] = 0,f[i] = g[i] = 0ll; }int main() {preprocess();int T; scanf("%d",&T);while(T--){scanf("%s",a+1); n = strlen(a+1); for(int i=1; i<=n; i++) a[i]-=96;for(int i=1; i<=n; i++) s1.str[i] = a[i]; s1.n = n;s1.get_sa();for(int i=1; i<=n; i++) s2.str[i] = a[n+1-i]; s2.n = n;s2.get_sa();for(int i=1; i+i<=n; i++){for(int j=i+i; j<=n; j+=i){if(a[j]==a[j-i]){int lb = j-LCS(j,j-i)+1,rb = j+LCP(j,j-i)-1;lb = max(lb+i-1,j); rb = min(rb,j+i-1);if(lb<=rb){f[lb]++; f[rb+1]--;g[lb-i-i+1]++; g[rb+1-i-i+1]--;}}}}for(int i=1; i<=n; i++) f[i] += f[i-1],g[i] += g[i-1];llong ans = 0ll;for(int i=1; i<n; i++){llong tmp = f[i]*g[i+1];ans += tmp;}printf("%lld\n",ans);clear();}return 0; } 發(fā)表于 2019-06-16 20:28 suncongbo 閱讀(...) 評(píng)論(...) 編輯 收藏 刷新評(píng)論刷新頁(yè)面返回頂部

總結(jié)

以上是生活随笔為你收集整理的UOJ #219 BZOJ 4650 luogu P1117 [NOI2016]优秀的拆分 (后缀数组、ST表)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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