洛谷1117 [NOI2016]优秀的拆分

Luogu

BZOJ

分析

发现一个 $\mathrm{AABB}$ 串是由两个 $\mathrm{AA}$ 串拼起来得到的。

设 $f[i]$ 表示以 $i$ 结尾的 $\mathrm{AA}$ 串的个数, $g[i]$ 表示以 $i$ 开头的 $\mathrm{AA}$ 串的个数。

那么有 $ans=\sum\limits_{i=1}^{n-1}f[i]\times g[i+1]$ 。

显然 $f$ 和 $g$ 可以暴力算,用 $\mathrm{hash}$ 可以做到 $O(n^2)$ ,然后就有 $95$ 分了。


为了剩下的 $5$ 分我们需要优化一下这个过程。

枚举 $\mathrm{A}$ 的长度 $len$ ,然后把所有位置为 $len$ 的倍数的点设为关键点。

显然一个满足要求的 $\mathrm{AA}$ 串会过两个关键点。

那么考虑相邻的两个关键点对答案的贡献。

设这两个关键点为 $x$ 和 $y$ ,首先就有 $y=x+len$ 。

记 $lcp$ 为后缀 $x$ 后缀 $y$ 的 $lcp$ 的长度, $lcs$ 为前缀 $x-1$ 前缀 $y-1$ 的 $lcs$ 的长度。

画图可知,如果 $lcp+lcs<len$ ,那么就不会构成 $\mathrm{AA}$ 串。

否则, $\mathrm{A}$ 的终点可以落在 $lcp$ 和 $lcs$ 的长度为 $lcp+lcs-len+1$ 的交上,因为这样子的话平移一下可以出现一个新的不重合的 $\mathrm{AA}$ 串。

然后因为 $\mathrm{A}$ 的起点和终点的位置都是一段区间,于是直接在 $f$ 和 $g$ 数组上差分即可。

上面说的可能不是很清楚,可以画图理解一下。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

const int N=30000+10;

int n,lg[N];
char s[N];
int x[N],y[N],z[N];

struct Suffix_Array {
    int sa[N],rnk[N],height[N];
    int st[16][N];
    
    inline void init() {
        memset(sa,0,sizeof(sa)),memset(rnk,0,sizeof(rnk));
        memset(height,0,sizeof(height)),memset(x,0,sizeof(x));
        memset(y,0,sizeof(y)),memset(z,0,sizeof(z));
    }
    
    inline void Suffix_Sort() {
        int m=122;
        for (re int i=1;i<=n;++i) ++z[x[i]=s[i]];
        for (re int i=2;i<=m;++i) z[i]+=z[i-1];
        for (re int i=n;i;--i) sa[z[x[i]]--]=i;
        for (re int k=1;k<=n;k<<=1) {
            int p=0;
            for (re int i=n-k+1;i<=n;++i) y[++p]=i;
            for (re int i=1;i<=n;++i) if (sa[i]>k) y[++p]=sa[i]-k;
            for (re int i=1;i<=m;++i) z[i]=0;
            for (re int i=1;i<=n;++i) ++z[x[i]];
            for (re int i=2;i<=m;++i) z[i]+=z[i-1];
            for (re int i=n;i;--i) sa[z[x[y[i]]]--]=y[i],y[i]=0;
            swap(x,y),x[sa[1]]=p=1;
            for (re int i=2;i<=n;++i)
                x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k])?p:++p;
            if (p==n) break; m=p;
        }
    }

    inline void Get_Height() {
        for (re int i=1;i<=n;++i) rnk[sa[i]]=i;
        for (re int i=1,j=0;i<=n;++i) {
            if (j) --j; int p=sa[rnk[i]-1];
            while (s[i+j]==s[p+j]) ++j;
            height[rnk[i]]=j;
        }
    }
    
    inline void build_ST() {
        memset(st,0x3f,sizeof(st));
        for (re int i=1;i<=n;++i) st[0][i]=height[i];
        for (re int i=1;i<=15;++i)
            for (re int j=1;j<=n;++j)
                st[i][j]=min(st[i-1][j],st[i-1][j+(1<<i-1)]);
    }
    
    inline void build() {
        init(),Suffix_Sort(),Get_Height(),build_ST();
    }

    inline int query(int x,int y) {
        if (rnk[x]>rnk[y]) swap(x,y);
        x=rnk[x]+1,y=rnk[y]; int t=lg[y-x+1];
        return min(st[t][x],st[t][y-(1<<t)+1]);
    }
} A,B;

int f[N],g[N];

int main() {
    for (re int i=2;i<N;++i) lg[i]=lg[i>>1]+1;
    int T; scanf("%d\n",&T);
    while (T--) {
        scanf("%s",s+1); n=strlen(s+1); A.build();
        reverse(s+1,s+n+1); B.build();
        fill(f+1,f+n+1,0),fill(g+1,g+n+1,0);
        for (re int len=1;len<=n/2;++len) {
            for (re int i=len,j=i+len;j<=n;i+=len,j+=len) {
                int lcp=min(A.query(i,j),len),lcs=min(B.query(n-i+2,n-j+2),len-1);
                if (lcp+lcs<len) continue;
                int t=lcp+lcs-len+1;
                ++g[i-lcs],--g[i-lcs+t],++f[j+lcp-t],--f[j+lcp];
            }
        }
        for (re int i=1;i<=n;++i) f[i]+=f[i-1],g[i]+=g[i-1];
        ll ans=0;
        for (re int i=1;i<n;++i) ans+=1ll*f[i]*g[i+1];
        printf("%lld\n",ans);
    }
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 37 PM

发表评论