洛谷P4762 [CERC2014] Virus synthesis 题解

题目链接：P4762 [CERC2014] Virus synthesis

题意：

病毒通常对您的健康有害。那么用……其他病毒来对抗它们怎么样呢？在这个问题中，您需要找出如何合成这种好的病毒。

我们为您准备了一组由字母 $\texttt{A}, \texttt{G}, \texttt{T}$ 和 $\texttt{C}$ 组成的字符串。它们对应于我们想要合成的病毒的 DNA 核苷酸序列，使用以下操作：

在现有序列的开头或末尾添加一个核苷酸。

复制序列，反转复制的片段，并将其粘贴到原始序列的开头或末尾（例如，$\tt AGTC$ 可以变成 $\tt AGTCCTGA$ 或 $\tt CTGAAGTC$）。

我们关心的是效率，因为我们有很多这样的序列，其中一些非常长。找出一种方法，以最少的操作次数合成它们。

输入格式：

输入的第一行包含测试用例的数量 $T$。接下来的每一行描述一个测试用例：

每个测试用例由一行非空字符串组成。字符串仅使用大写字母 $\texttt{A}, \texttt{C}, \texttt{G}$ 和 $\tt T$，长度不超过 $100,000$ 个字符。

输出格式：

对于每个测试用例，输出一行，包含构建给定序列所需的最少操作总数。

$\mathcal{Part}\ 1$

题目的描述很有意思，这不禁让我们提出一个疑问：真的存在可以对抗病毒的病毒吗？

事实上真的有这种病毒，他们称为噬病毒体（Virophage），通常与巨型病毒共同感染。

噬病毒体依靠共同感染的巨型病毒的病毒复制工厂进行自身复制，并且这个过程会导致巨型病毒失活。

更有意思的是，这种病毒的确是双链 DNA 病毒，符合题目的描述。~~怀疑出题人对生物学有不少研究。~~

除此以外，题目描述写的是 fighting ，亦有“竞争”之意。

这让人联想到噬菌体，他们虽然不直接攻击别的病毒，但是会使宿主细胞裂解

这实际上破坏了其他能感染这种宿主细胞的病毒的生存坏境，因此他们的确构成竞争关系。

$\mathcal{Part}\ 2$

~~不过以上知识对这道题的解法没有提供任何帮助。~~

注意到第二种操作（复制序列的操作）相对于第一种操作一定不劣

对于一个偶回文串 $A$ ，如果在它两头加上一个相同的字符可以得到 $B$ ，

那么 $B$ 的操作数至多为 $A$ 的操作数加 $1$ ，因为我们可以构造半个 $A$ 并添加上这个字符，再复制它。

考虑对给定字符串构建 PAM （回文自动机），并额外维护每个偶回文串的不超过其长度一半的最长回文后缀。

这个最长回文后缀可以通过跳 fail 树得到，总复杂度是线性的。

设 $f(u)$ 为节点 $u$ 的答案，则最终答案为 $\min\{\,f(u) + n - \mathrm{len}(u)\}$ 。

我看题解区好多都跑了一遍 bfs ，实际上不需要的。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
#define check(p) ((len[p] + 2) * 2 > len[tot])

char s[N]; queue<int> q;
int tot, id[26], fail[N], len[N], mx[N], dp[N], ch[N][4];
int getfail(int p, int i)
{
    while(s[i - len[p] - 1] != s[i]) p = fail[p];
    return p;
}
int getmax(int p, int i)
{
    while(s[i - len[p] - 1] != s[i] || check(p)) p = fail[p];
    return p;
}
void solve()
{
    cin >> (s + 1); int n = strlen(s + 1), res = n;
    for(int i = 0; i <= tot; i++) {
        fail[i] = len[i] = mx[i] = dp[i] = 0;
        for(int j = 0; j < 4; j++) ch[i][j] = 0;
    }
    fail[tot = 1] = 0; len[0] = -1; dp[1] = 1;
    for(int i = 1, p, c; i <= n; i++)
    {
        c = id[s[i] - 'A']; p = i > 1 ? getfail(p, i) : 0;
        if(!ch[p][c])
        {
            ch[p][c] = ++tot; len[tot] = len[p] + 2; 
            fail[tot] = p > 0 ? ch[getfail(fail[p], i)][c] : 1;
            mx[tot] = len[tot] > 2 ? ch[getmax(mx[p], i)][c] : fail[tot];
            if(len[tot] & 1) dp[tot] = len[tot];
            else down(dp[tot] = dp[p] + 1, dp[mx[tot]] + 1 + len[tot] / 2 - len[mx[tot]]);
        }
        p = ch[p][c]; down(res, dp[p] + n - len[p]);
    }
    cout << res << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    id[0] = 0, id[19] = 1; id[6] = 2; id[2] = 3;
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}