题解：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

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

$l\le x\wedge y\le r\wedge 2\nmid y-x\wedge s_{x,y}\text{is Palidrome}$ ： $[x,y]$ 被 $[l,r]$ 包含，且 $s_{x,y}$ 是长度为偶数的回文串。
$f_{x,\lfloor\frac{x+y}{2}\rfloor}$ ：回文串的左半部分。
$+1$ ：意思是把回文串的左半部分复制一遍反转插到右边。这就可以发现 $f_{x,\lfloor\frac{x+y}{2}\rfloor}+1=f_{x,y}$ 。
$+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 的）；如果“去掉一半”的区间有相交，那又容易有一个更长的“半个区间”覆盖掉这些相交的“半个区间”。所以这个代码是极其难卡的。

代码：

CPP

#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 的代码就写完了。

题解：P4762 - [CERC2014] Virus synthesis

文章操作

相关推荐

评论

题解：P4762 - [CERC2014] Virus synthesis