洛谷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;
}