题目大意:
定义一个字符串的拆分是优秀的当且仅当是 \(AABB\) 的形式, 求给定字符串的所有子串的所有的拆分中有多少是优秀的.
思路:
95 分太好拿了, 这里直接考虑正解该怎么做.
不难发现我们只需要求出每个点开头的 \(AA\) 形式的字符串和每个点结尾的 \(AA\) 字符串, 然后枚举分割点两边乘起来就好了. 可是关键是 \(AA\) 形式的字符串可能有 \(n^2\) 个, 直接枚举的话一定不是正解.
考虑分长度来处理所有的这种子串, 对于长度为 \(2\times len\) 的 \(AA\) 形式的子串, 我们将原串每隔 \(len\) 就建立一个关键点, 不难发现所有长度为 \(2\times len\) 的子串必定可以表示为两个关键点前面接一个 lcs, 后面接一个 lcp, 并且 lcs 和 lcp 的部分有重叠, 重叠的部分就是可以作为两个 \(A\) 分割点的地方, 得到了分割点,\(AA\) 的起点和终点的范围也就知道了.
于是我们只需要枚举每两个关键点, 然后实现区间加法, 单点查询即可.
- /*=======================================
- * Author : ylsoi
- * Time : 2019.2.6
- * Problem : luogu1117
- * E-mail : ylsoi@foxmail.com
- * ====================================*/
- #include<bits/stdc++.h>
- #define REP(i,a,b) for(int i=a,i##_end_=b;i<=i##_end_;++i)
- #define DREP(i,a,b) for(int i=a,i##_end_=b;i>=i##_end_;--i)
- #define debug(x) cout<<#x<<"="<<x<<" "
- #define fi first
- #define se second
- #define mk make_pair
- #define pb push_back
- typedef long long ll;
- typedef unsigned long long ull;
- using namespace std;
- void File(){
- freopen("luogu1117.in","r",stdin);
- freopen("luogu1117.out","w",stdout);
- }
- template<typename T>void read(T &_){
- _=0; T fl=1; char ch=getchar();
- for(;!isdigit(ch);ch=getchar())if(ch=='-')fl=-1;
- for(;isdigit(ch);ch=getchar())_=(_<<1)+(_<<3)+(ch^'0');
- _*=fl;
- }
- const int maxn=3e4+10;
- int T,n,Log[maxn];
- struct Suffix_Array{
- char s[maxn];
- int sz,sa[maxn],rk[maxn],tp[maxn],tax[maxn],height[maxn];
- int st[maxn][15];
- void radix_sort(){
- REP(i,1,sz)tax[i]=0;
- REP(i,1,n)++tax[rk[i]];
- REP(i,1,sz)tax[i]+=tax[i-1];
- DREP(i,n,1)sa[tax[rk[tp[i]]]--]=tp[i];
- }
- void suffix_sort(){
- memset(rk,0,sizeof(rk));
- memset(sa,0,sizeof(sa));
- memset(tp,0,sizeof(tp));
- sz=26;
- REP(i,1,n)rk[i]=s[i]-'a'+1,tp[i]=i;
- radix_sort();
- for(int w=1,p=0;w<n;w<<=1){
- p=0;
- REP(i,1,w)tp[++p]=n-w+i;
- REP(i,1,n)if(sa[i]>w)tp[++p]=sa[i]-w;
- radix_sort();
- swap(rk,tp);
- rk[sa[1]]=p=1;
- REP(i,2,n)
- if(tp[sa[i-1]]==tp[sa[i]] && tp[sa[i-1]+w]==tp[sa[i]+w])rk[sa[i]]=p;
- else rk[sa[i]]=++p;
- sz=p;
- if(sz==n)break;
- }
- int p=0;
- REP(i,1,n){
- if(p)--p;
- int j=sa[rk[i]-1];
- while(s[i+p]==s[j+p])++p;
- height[rk[i]]=p;
- }
- REP(i,1,n)st[i][0]=height[i];
- REP(j,1,Log[n])
- REP(i,1,n-(1<<j)+1)
- st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
- }
- int lcp(int x,int y){
- x=rk[x],y=rk[y];
- if(x>y)swap(x,y);
- ++x;
- int d=Log[y-x+1];
- return min(st[x][d],st[y-(1<<d)+1][d]);
- }
- }S[2];
- ll pre[maxn],nex[maxn];
- void work(){
- memset(pre,0,sizeof(pre));
- memset(nex,0,sizeof(nex));
- REP(len,1,n/2){
- if(len==1){
- REP(i,1,n-1)if(S[0].s[i]==S[0].s[i+1]){
- ++pre[i],--pre[i+1];
- ++nex[i+1],--nex[i+2];
- }
- continue;
- }
- for(int i=len*2;i<=n;i+=len){
- int j=i-len;
- int l=max(j-S[1].lcp(n-j+1,n-i+1)+1,j-len+1);
- int r=min(j+S[0].lcp(j,i)-len,j);
- //debug(j),debug(i)<<endl;
- if(l<=r){
- ++pre[l],--pre[r+1];
- //cout<<l<<" "<<r<<endl;
- l+=len*2-1,r+=len*2-1;
- ++nex[l],--nex[r+1];
- //cout<<l<<" "<<r<<endl;
- }
- }
- }
- REP(i,1,n){
- pre[i]+=pre[i-1];
- nex[i]+=nex[i-1];
- }
- /*REP(i,1,n)printf("%lld",pre[i]);
- printf("\n");
- REP(i,1,n)printf("%lld",nex[i]);
- printf("\n");*/
- ll ans=0;
- REP(i,1,n-1)ans+=nex[i]*pre[i+1];
- printf("%lld\n",ans);
- }
- int main(){
- // File();
- REP(i,2,3e4)Log[i]=Log[i>>1]+1;
- read(T);
- while(T--){
- scanf("%s",S[0].s+1);
- strcpy(S[1].s+1,S[0].s+1);
- n=strlen(S[0].s+1);
- reverse(S[1].s+1,S[1].s+n+1);
- S[0].suffix_sort();
- S[1].suffix_sort();
- work();
- }
- return 0;
- }
[bzoj4650][Noi2016] 优秀的拆分 -- 后缀数组
来源: http://www.bubuko.com/infodetail-2946761.html