P3900 图森题解

dspt · 2024-03-13 15:00:09 · 题解

据我所知，这题原名叫：图样图森破，意思是：too young too simple

网上题解比较少，感觉略显复杂，于是我写了篇题解，思路应该算比较简单，但有些部分缺少严谨的证明。

约定：对于字符串 T，记 |T| 表示 T 的长度，T_i 为 i 个 T 拼接得到的字符串，T[l:r] 表示 T 从第 l 个字符开始到第 r 个字符构成的子串，s_{i,j} 表示 s_i 的第 j 个字符，记 \text{R}(T) 为 T 翻转后得到字符串。

考虑 n=1 的情况，手玩可以发现，设仅有的字符串为 T，若 T_2 有一个回文子串 T_2[l:r] 满足：(l=1\lor r=2|T|) \land (r-l+1\ge|T|)，答案即为 Infinity，否则答案为 \max|T_2[l:r]|。

说人话就是，n=1 并且答案为 Infinity 的情况有如下两种：

其实可以感性归纳证明。例如 $|T|=7$，$T_2[1:9]$ 的是一个回文字符串，在 $T_2$ 左侧再拼一个 $T$，则 $T_3[8:16]$ 是一个回文串。由回文串的性质得 $T_3[17:21]=T_3[3:7]=\text R(T_3[3:7])$，即将 $T_3[8:16]$ 拓展到 $T_3[3:21]$，$T_3[3:21]$ 也是一个回文串，这样就把回文串的长度由 $[|T|+1,2|T|)$ 拓展到了 $[2|T|+1,3|T|)$。由归纳法，回文串长度可以无限拓展，故答案为 Infinity。

好消息是第一种情况包含于第二种情况，我们只需要判断一下 T_2 是否有在边界并且长度大于 |T| 的回文字符串即可。如果答案不为 Infinity，则答案为 T_2 的最长回文子串的长度。若 n>1，此长度为答案下界（现在的五个 Hack 就是 Hack 这里）。

回文匹配的话可以用 Manacher 或者二分哈希，当然我们后面还需要解决 n>1 的情况，所以用二分哈希更合适。将每个串及其反串分别预处理哈希值，可以在 O(1) 的时间内取出一个子串的哈希值。我们只需要枚举回文中心的一两个字符，二分向两侧拓展至最大长度即可。

至此，n=1 的情况就处理完了，注意到 n=1 的 L 为 100000，比其它情况的 L 要大很多，所以要特判。

考虑 n>1 的情况，设某个时刻答案来自于字符串 T。容易发现，对于任何一个 T，我们并不关心其内部构造，我们只需要知道 T 的端点分别在哪两个字符串中就好了，记 f_{i,l,j,r} 表示左端点为 s_{i,l} ，右端点为 s_{j,r} 的 T 的最大回文子串长度。并且我们限制任意一个状态无法拓展，即 l=1\lor r=|s_j|\lor s_{i,l-1}\neq s_{j,r+1}。

那么状态可以转移当且仅当 l=1\lor r=|s_j|。若 l=1\land r=|s_j|，则 T 本身为回文串，答案为 Infinity。考虑剩下的转移：

若 l=1，代表可在 T 的左侧加上满足 s_{k,|sk|}=s_{j,r+1} 的 s_k，并向两侧拓展。

若 r=|s_j|，代表可在 T 的右侧加上满足 s_{k,1}=s_{i,l-1} 的 s_k，并向两侧拓展。

容易发现转移构成了一个图，并且这个图上是有环的。这时我们令 w=10^5\ge nL，若某一时刻答案超过 w，则认为答案为 Infinity。

但是这个状态也太多了，我们需要考虑优化。注意到若 l>1\land r<|s_j|，这个状态没有出边，在这个答案更新完后我们直接丢弃这个状态。也就是说，现在需要转移的状态要么 l=1 要么 r=|s_j|，那就可以舍弃 l,r 这两维，加入一维 k 表示这两种情况是哪种。

这类似于动态规划的过程，但我们没法找到一个合适的 DP 顺序，又因为转移构成了一张图，可以用 BFS 进行这个过程。一开始，我们先对每个字符串本身进行暴力拓展，找到一个可以往下转移的情况，把它加入队列。注意，还有种情况是开始的回文字符串是偶数，且回文分界线在两个字符串之间，比如 s_1=\tt cedba，s_2=\tt bad，这时就要把 (1,3,1) 加入队列（第三个元素为 0 表示 l=1，为 1 表示 r=|s_j|）。另外我们还可以使用一些剪枝技巧，若某个状态出队时，发现自己的答案小于 f_{i,j,k}，即在它待在队列里的这段时间，状态 (i,j,k) 的答案已经被更新过了，这时可以直接暂时不更新这个状态。

关于此方法的正确性和时间复杂度，我不是特别清楚，但可以通过原题数据和现在的五个 Hack 数据。我的哈希常数比较大，当 n=1 时，O(L\log L) 的算法最慢的点用时在 0.9s 左右，当 n>1 时，O(n^2L\log L) 的算法最慢的点用时在 0.5s 左右。

代码：4.08 KB，4.06 s

写了注释，应该算比较简洁易懂了吧。自己写的时候压行压到了 65 行，代码仅有 3.46 KB。

#include <queue>
#include <time.h>
#include <random>
#include <iostream>
using namespace std;
typedef const int ci; ci p((1 << 30) - 35); // 哈希模数
int a[200002] = {1}, b[200002] = {1}; // 多项式哈希，每位的幂值和逆元
int c[26], f[101][1001][2];           // 每个字母的哈希值，(i,j,k) 的答案
struct hash {
    int m; string s; vector<int> h[2]; // 哈希表，h0 为正向哈希表，h1 为逆向哈希表
    void init(const int t) { h[0].resize(t + 2); h[1].resize(t + 2); } // 初始化
    void build() // 建哈希表
    {
        for (int i(1); i <= m; ++i) h[0][i] = ((long long)c[s[i] - 'a'] * a[i] + h[0][i - 1]) % p;
        for (int i(m); i; --i) h[1][i] = ((long long)c[s[i] - 'a'] * a[m - i + 1] + h[1][i + 1]) % p;
    }
    void read() { cin >> s; m = s.size(); s = ' ' + s; build(); }
    int get(ci l, ci r, const bool t) // 查询 s[l:r] 的哈希值，t = 0 则为正向，t = 1 则为反向
    {
        return (t ? (long long)(h[1][l] - h[1][r + 1] + p) * b[m - r + 1]
                  : (long long)(h[0][r] - h[0][l - 1] + p) * b[l]) % p;
    }
} e[101];
int expand(ci i, ci l, ci j, ci r) // 二分，现在的状态左端点为 s(i,l) 右端点为 s(j,r)，返回可以向左和向右的最大长度
{
    int L(1), R(min(l - 1, e[j].m - r)), p(0);
    while (L <= R)
        if (ci t(L + R >> 1); e[i].get(l - t, l - 1, 0) == e[j].get(r + 1, r + t, 1)) p = t, L = t + 1;
        else R = t - 1;
    return p;
}
struct node { int i, j, v; bool k; }; queue<node> q; // BFS 队列
int main()
{
    mt19937 r(time(0)); uniform_int_distribution<int> d(1, p - 1);
    for (int i(0); i < 26; ++i) c[i] = d(r); // 处理每个字符的哈希值，用 mt19937 提高准确性，放止被卡
    for (int i(1); i <= 2e5; ++i)
        a[i] = (long long)a[i - 1] * 1073741783 % p, b[i] = (long long)b[i - 1] * 894784824 % p;
        // 处理每位的哈希值，1073741783 是一个大质数，894784824 是它在 mod p 意义下的逆元
    int n, w(0); cin >> n;
    // 为了方便，用 e[0] 记录 TT，大小要开两倍
    if (n == 1) e[0].init(2e5); else e[0].init(2e3); // 如果 n = 1，初始化的大小为 2e5
    for (int i(1); i <= n; ++i) e[i].init(n < 2 ? 1e5 : 1e3), e[i].read();
    #define INF { cout << "Infinity\n"; return 0; } // 答案为 Infinity，结束程序
    #define push(x, y) if (L == 1 && R == e[y].m) INF \ 
                       if (t > w) w = t; if (w > 1e5) INF \
                       if (L == 1) if (f[y][R][0] < t) q.emplace((node){y, R, f[y][R][0] = t, false}); \
                       if (R == e[y].m) if (f[x][L][1] < t) { q.emplace((node){x, L, f[x][L][1] = t, true}); }
                     // 将 (x, L, y, R) 弹入队列 更新答案，若答案超过 1e5，答案为 Infinity
    for (int i(1); i <= n; ++i)
    {
        for (int j(1); j <= e[i].m; ++j) e[0].s = e[i].s + e[i].s.substr(1);
        e[0].m = e[i].m << 1; e[0].h[1][e[0].m + 1] = 0; e[0].build(); // 构建 TT
        for (int j(1); j <= e[0].m; ++j) // 长度为奇数
        {
            ci k(expand(0, j, 0, j)), L(j - k), R(j + k); if ((k << 1 | 1) > w) w = k << 1 | 1;
            if (L <= e[i].m && R > e[i].m && (L == 1 || R == e[0].m)) INF
        }
        for (int j(1); j < e[0].m; ++j) if (e[0].s[j] == e[0].s[j + 1]) // 长度为偶数
        {
            ci k(expand(0, j, 0, j + 1)), L(j - k), R(j + 1 + k); if ((k + 1 << 1) > w) w = k + 1 << 1;
            if (L <= e[i].m && R > e[i].m && (L == 1 || R == e[0].m)) INF
        }
        if (n == 1) { cout << w << '\n'; return 0; } // n = 1，程序可以直接结束
        // 用 t 记录拓展后的答案
        for (int j(1); j <= e[i].m; ++j) { ci k(expand(i, j, i, j)), L(j - k), R(j + k), t(k << 1 | 1); push(i, i) }
        for (int j(1); j < e[i].m; ++j) if (e[i].s[j] == e[i].s[j + 1])
        { ci k(expand(i, j, i, j + 1)), L(j - k), R(j + 1 + k), t(k + 1 << 1); push(i, i) }
    }
    // 字符串子串长度为偶数，且中心分界线正好在两个字符串之间的情况分别枚举两个字符串即可
    for (int i(1); i <= n; ++i) for (int j(1); j <= n; ++j)
    { ci k(expand(i, e[i].m + 1, j, 0)), L(e[i].m + 1 - k), R(k), t(k << 1); if (k) { push(i, j); } }
    while (!q.empty()) { // BFS 更新
        const node u(q.front()); q.pop();
        for (int i(1); i <= n; ++i)
        if (u.k) {
            ci k(expand(u.i, u.j, i, 0)), L(u.j - k), R(k), t(u.v + (k << 1));
            if (k) { push(u.i, i) }
        } else {
            ci k(expand(i, e[i].m + 1, u.i, u.j)), L(e[i].m + 1 - k), R(u.j + k), t(u.v + (k << 1));
            if (k) { push(i, u.i) }
    }   } cout << w << endl; return 0;
}

P3900 图森 题解

P3900 图森题解