题解：P4762 - [CERC2014] Virus synthesis

· · 题解

距离作者发这个帖子已经过去了三天，但是没有任何一个人能够卡掉我的代码，于是来写一发题解。本题解随时欢迎 Hack。

设串为 s，s_{l,r} 表示 s_l,s_{l+1},s_{l+2},...,s_r 依次拼接而成的串。

我们容易想到一个区间 dp。设 f_{l,r} 表示把 s_{l,r} 凑出来需要的最小操作次数。容易得到边界和转移：

f_{i,i}=1\\ f_{l,r}=\min_{l\le x\wedge y\le r\wedge 2\nmid y-x\wedge s_{x,y}\text{is Palidrome}}f_{x,\lfloor\frac{x+y}{2}\rfloor}+1+x-l+r-y

下面那一长串公式是干什么的呢？我们来逐步拆解一下。

这就是我们的区间 dp。

不难想到把“区间 dp”转化为递归，然后就可以执行一些剪枝了。我们设一个函数 dac(l,r) 表示求出 f_{l,r} 的值。

设 rg_i 表示以 i 为中心的最长回文串的半径，我们可以用 Manacher 在 O(r-l+1) 时间内求出 rg。这就相当于知道了区间里的所有回文串。

考虑：如果有两个回文串 s_{l_1,r_1} 和 s_{l_2,r_2} 且 [l_1,r_1]\subseteq[l,r]\wedge[l_2,r_2]\subseteq[l,r]\wedge[l_2,r_2]\subseteq[l_1,r_1]，那么一定有 f_{l_1,r_1}+l_1-l+r-r_1\le f_{l_2,r_2}+l_2-l+r-r_2，这个时候我们就不用执行 dac(l_2,r_2)。

所以我们把区间的所有回文串求出来之后，把以每一个点为中心的最长回文串对应的区间放到一个 std::vector 里面，然后把里面所有被其他区间包含的区间去掉，剩下的区间一定是没有包含关系的。

怎么去掉“被包含”的区间？我们把区间按照 l 为第一关键字从小到大、r 为第二关键字从大到小排序，如果一个区间的 r 不大于前面区间的 r 的最大值，那这个区间肯定就是被包含了的，因为它的 l 不小于前面所有区间的 l，且 r 也不大于前面某个区间的 r。

然后对于剩下的区间，我们全部去掉一半之后递归即可。

为什么这个能过呢？

你注意到，如果所有“去掉一半”的区间没有相交，那么单个 dac 区间长度每次至少减半，总时间复杂度 O(n\log^2 n)（多一个 \log 是 std::sort 的）；如果“去掉一半”的区间有相交，那又容易有一个更长的“半个区间”覆盖掉这些相交的“半个区间”。所以这个代码是极其难卡的。

代码：

#include <cstdio>
#include <vector>
#include <algorithm>
#include <unordered_map>
const int MAXN = 2e5 + 7;
int T, n, rg[MAXN];
char s[MAXN];
std::unordered_map<long long, int> mp;
inline void read(int &x)
{ // 这是快读，读入一个正整数（没有判负号）
    x = 0;
    char c = getchar();
    while (c < '0' || c > '9')
        c = getchar();
    while (c >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + (c & 15), c = getchar();
}
inline void read()
{ // 读入一个字符串，并在两边和每两个字符之间加入'|'字符
    s[n = 1] = '|', mp.clear();
    char c = getchar();
    while (c < 'A' || c > 'Z')
        c = getchar();
    while (c >= 'A' && c <= 'Z')
        s[++n] = c, s[++n] = '|', c = getchar();
}
struct Range
{ // struct 区间
    int l, r;
    inline bool operator<(const Range &rhs) const
    { // 这个是为了准备排序，去重用的
        return l == rhs.l ? r + r - l > rhs.r + rhs.r - rhs.l : l < rhs.l;
    }
};
inline int dac(int l, int r)
{
    if (mp.count((long long)(l)*MAXN + r))  // 记忆化，如果已经算过这个区间的答案
        return mp[(long long)(l)*MAXN + r]; // 直接返回
    for (int i = l; i <= r; ++i)
        rg[i] = 0;                       // 把以每个点为中心的最长回文串半径置为0
    int mxr = 0, ans = (r - l + 1) >> 1; // 由于'|'字符的存在，所以区间内实际字母数是(r-l+1)>>1
    for (int i = l, j = 0, k = 1; i <= r; i += k)
    { // Manacher 模板
        while (i - j - 1 >= l && i + j + 1 <= r && s[i - j - 1] == s[i + j + 1])
            ++j;
        rg[i] = j;
        for (k = 1; k <= j; ++k)
        {
            if (rg[i] - k == rg[i - k])
                break;
            rg[i + k] = std::min(rg[i] - k, rg[i - k]);
        }
        j = std::max(j - k, 0), s[i] == '|' && (mxr = std::max(mxr, rg[i])); // 限制s[i]=='|'的原因是我们要找到所有长度为偶数的回文串来递归
    }
    if (mxr < 2)                                               // 如果区间内没有长度超过1的回文串
        return mp[(long long)(l)*MAXN + r] = (r - l + 1) >> 1; // 直接返回区间内字符数
    std::vector<Range> rgs;
    std::vector<bool> nv(r - l + 1, false);
    for (int i = l; i <= r; ++i)
        if (s[i] == '|' && rg[i])                         // i作为一个长度为偶数的回文串的串中心
            rgs.push_back({i - rg[i], i});                // 注意我们只放进去了“一半区间”，对应的完整区间是[l,r+(r-l)]
    std::sort(rgs.begin(), rgs.end());                    // 注意operator<是排序的“完整区间”
    for (int i = 0, lst = -1; i < (int)(rgs.size()); ++i) // 对于所有区间
        if ((~lst) && (rgs[i].r + rgs[i].r - rgs[i].l <= rgs[lst].r + rgs[lst].r - rgs[lst].l))
            nv[i] = true; // 由于我们已经按照左端点排序，所以如果右端点被包含，就说明这个区间被完整包含了
        else
            lst = i; // 那么这个区间就没有被完整包含，就说明可以留下它
    for (int i = 0; i < (int)(rgs.size()); ++i)
        if (!nv[i]) // 所有nv=true的区间都是“没有被留下的”
            ans = std::min(ans, ((r - l + 1) >> 1) - rgs[i].r + rgs[i].l + dac(rgs[i].l, rgs[i].r) + 1);
            // 区间总字符数-回文串总长度+dac(回文串的一半区间)+1
            // 其实也就是去掉回文串剩余字符数+回文串的最小操作次数
    rgs.clear(); // 防止空间爆炸
    return mp[(long long)(l)*MAXN + r] = ans;
}
int main()
{
    read(T);
    while (T--)
        read(), printf("%d\n", dac(1, n));
    return 0;
}

由于 Manacher 的 2 倍常数，最慢的点跑到了 1.6 秒，肯定干不过回文自动机。但是这个思路是暴力剪枝过来的，十分好理解。

上面是我的考场代码（已经过 VSCode C++ 插件格式化），肯定很丑，赛后我给我旁边的同学讲了思路以后，他用不到 1.5K 的代码就写完了。