LG1117 [NOI2016]优秀的拆分

发布于 2020-07-21  2.58k 次阅读


P1117

跟这道题很像:CF319D(这也是黑色的)(和我写的这道题的的博客

分析

这是一道后缀SA+ST的题目,但是众所周知字符串哈希是一种异常优秀的算法,所以我们使用字符串哈希解决这一道问题。在这道题中字符串哈希相比于SA的方法虽然慢了一个$O(logn)$,但是依旧在复杂度可承受范围内。

在这道题中我们需要求出拆分为AABB形态的方案数量。而我们发现AABB形态就是由两个AA状态的字符串连接形成。

如果我们设$A_i$表示以i位结尾的AA串数量,以$B_i$表示以i位开头的AA串数量。则很显然若我们将第i位及以前的部分放一个AA串,在第i+1及以后放一个AA串,他们就可以连在一起成为一个AABB串,所以当前状态对答案的贡献即为$A_i * B_i$。

如果我们可以求解出$A$和$B$,则答案即为:

$$\sum\limits_{i=1}^{n-1}A_i*B_{i+1}$$

现在的问题就是如何求解出A数组与B数组。

如果我们在字符串上每隔$len$设置一个观察点,相邻观察点的最长公共前缀(LCP)与最长公共后缀(LCS)加起来构成的字符串即为经过两点上的最长相同串,并且若$LCP+LCS>=len$,说明它们相交。若相交有重叠部分,则我们可以通过平移得到多个可行的摆放方案,可以缩短两个区间的尾部,也可以缩短两个区间的头部以使他们不重合(详见代码)。

至于如何求LCP和LCS,当然可以用SA,不过我们这里还是采用字符串哈希,毕竟它写起来十分简易。

代码

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
const int maxn = 30005;

int a[maxn], b[maxn];
long long w[maxn], p[maxn];
char s[maxn];

inline int get(int l, int r)
{ //计算字符串中l~r段的哈希值
    return ((w[r] - w[l - 1] * p[r - l + 1]) % mod + mod) % mod;
}

int n, now;

int lcp(int x, int y) //求最长前缀
{
    int l = 0, r = now;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (get(x - mid + 1, x) == get(y - mid + 1, y))
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

int lcs(int x, int y) //求最长后缀
{
    int l = 0, r = n - y + 1;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (get(x, x + mid - 1) == get(y, y + mid - 1))
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        scanf("%s", s + 1);
        n = strlen(s + 1);
        p[0] = 1;
        for (int i = 1; i <= n; i++)
        { //字符串哈希
            p[i] = p[i - 1] * 31 % mod;
            w[i] = (w[i - 1] * 31 + s[i] - 'a') % mod;
        }
        for (int len = 1; len <= n; len++)
        {                              //从小到大枚举删除区间的长度
            int j = len, k = len << 1; //两个观察点
            now = len;
            while (k <= n)
            {
                int LCP = lcp(j, k), LCS = lcs(j, k);
                int hd = max(k - LCP + len, k), tl = min(k + LCS - 1, k + len - 1); //两个块的尾位置
                if (hd <= tl)
                {
                    a[hd]++, a[tl + 1]--;                         //两个尾部之间的空间
                    b[hd - len * 2 + 1]++, b[tl - len * 2 + 2]--; //两个头部之间的空间
                }
                j += len, k += len; //转移到下一个观察点
            }
        }
        for (int i = 1; i <= n; i++)
            a[i] += a[i - 1], b[i] += b[i - 1];
        long long answer = 0;
        for (int i = 1; i < n; i++)
            answer += a[i] * b[i + 1];
        printf("%lld\n", answer);
    }
    return 0;
}

我缓慢吐出一串啊吧啊吧并不再想说话