[NOI 2016]优秀的拆分

Description

题库链接

给你一个长度为 \(n\) 的只含小写字母的字符串 \(S\) ，计算其子串有多少优秀的拆分。

如果一个字符串能被表示成 \(AABB\) 的形式，其中 \(A,B\) 非空，那么称 \(AABB\) 是一个优秀的拆分。一个子串可能有多个优秀的拆分。

多组询问，询问组数 \(T\) 。

\(1\leq n\leq 30000,1\leq T\leq 10\)

Solution

会用这题的方法的话，应该不难想。

如果记 \(s_{1_i}\) 为以 \(i\) 结尾的 \(AA\) 串个数，记 \(s_{2_i}\) 为以 \(i\) 开头的 \(BB\) 串个数。

那么答案就是 \(\sum\limits_{i=2}^n s_{1_{i-1}}\times s_{2_i}\)

考虑如何求 \(s_1\) 或 \(s_2\) 。

我们可以枚举 \(A\) 的长度 \(l\) ，用 \(i,i+l\) 这两个点可以将所有的长度为 \(2l\) 的 \(AA\) 并且同一个长度为 \(2l\) 的 \(AA\) 不会被不同的一组 \(i,i+l\) 固定。

这样对于每一组 \(i,i+l\) ，我们设法去计算它所固定的长度为 \(2l\) 的 \(AA\) 。

可以求出 \(i,i+l\) 的最长公共前缀 \(x\) ， \(i,i+l\) 的最长公共后缀 \(y\) ，如果 \(x+y\geq l\) ，那么存在长度为 \(2l\) 的 \(AA\) 经过 \(i,i+l\) 。

求出区间左端点 \(L=\max\{i-x+1, i-l+1\}\) ，右端点 \(R=\min\{i-l+y+1, i\}\) 。

显然这一段区间都是能够对答案产生贡献的，差分一下即可。

~~下发的几个样例字符串长度都是递增的...大样例过了自信 AC ，结果因为没清空数组 wa 成苟~~

Code

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 30000+5;

int bin[35], lgn[N], t, n, m, x[N<<1], y[N<<1], c[N];

ll s1[N], s2[N];

struct SA {

    char ch[N];

    int sa[N], rk[N], height[N], f[30][N];

    void get() {

        for (int i = 1; i <= n*2; i++) x[i] = y[i] = 0;

        for (int i = 1; i <= m; i++) c[i] = 0;

        for (int i = 1; i <= n; i++) c[x[i] = ch[i]]++;

        for (int i = 2; i <= m; i++) c[i] += c[i-1];

        for (int i = n; i >= 1; i--) sa[c[x[i]]--] = i;

        for (int k = 1; k <= n; k <<= 1) {

            int num = 0;

            for (int i = n-k+1; i <= n; i++) y[++num] = i;

            for (int i = 1; i <= n; i++) if (sa[i] > k) y[++num] = sa[i]-k;

            for (int i = 1; i <= m; i++) c[i] = 0;

            for (int i = 1; i <= n; i++) c[x[i]]++;

            for (int i = 2; i <= m; i++) c[i] += c[i-1];

            for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i];

            swap(x, y); x[sa[1]] = num = 1;

            for (int i = 2; i <= n; i++)

                x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k]) ? num : ++num;

            if ((m = num) == n) break;

        }

        for (int i = 1; i <= n; i++) rk[sa[i]] = i;

        for (int i = 1, k = 0; i <= n; i++) {

            if (rk[i] == 1) continue;

            if (k) --k; int j = sa[rk[i]-1];

            while (i+k <= n && j+k <= n && ch[i+k] == ch[j+k]) ++k;

            height[rk[i]] = k;

        }

    }

    void rmq() {

        int t = lgn[n];

        for (int i = 1; i <= n; i++) f[0][i] = height[i];

        for (int i = 1; i <= t; i++)

            for (int j = 1; j+bin[i-1] <= n; j++)

                f[i][j] = min(f[i-1][j], f[i-1][j+bin[i-1]]);

    }

    int lcp(int a, int b) {

        a = a > n ? 0 : rk[a], b = b > n ? 0 : rk[b];

        if (a > b) swap(a, b); ++a;

        int t = lgn[b-a+1];

        return min(f[t][a], f[t][b-bin[t]+1]);

    }

}b, f;

void work() {

    bin[0] = 1; for (int i = 1; i <= 25; i++) bin[i] = (bin[i-1]<<1);

    lgn[0] = -1; for (int i = 1; i < N; i++) lgn[i] = lgn[i>>1]+1;

    scanf("%d", &t);

    while (t--) {

        memset(s1, 0, sizeof(s1)), memset(s2 ,0, sizeof(s2));

        scanf("%s", f.ch+1); n = strlen(f.ch+1);

        for (int i = 1; i <= n; i++) b.ch[n-i+1] = f.ch[i];

        m = 255; f.get(); f.rmq(); m = 255; b.get(); b.rmq();

        for (int l = 1; l <= n; l++)

            for (int i = 1; i+l <= n; i += l) {

                int x = b.lcp(n-i+1, n-(i+l)+1), y = f.lcp(i+1, i+l+1);

                if (x+y < l) continue;

                int L = max(i-x+1, i-l+1), R = min(i-l+y+1, i);

                if (L > R) continue;

                s1[L+l*2-1]++, s1[R+l*2]--;

                s2[L]++, s2[R+1]--;

            }

        for (int i = 2; i <= n; i++) s1[i] += s1[i-1], s2[i] += s2[i-1];

        ll ans = 0;

        for (int i = 2; i <= n; i++) ans += 1ll*s1[i-1]*s2[i];

        printf("%lld\n", ans);

    }

}

int main() {work(); return 0; }

巴特西

[NOI 2016]优秀的拆分

Description

Solution

Code

最新文章

热门文章