题解 P4762 Virus synthesis

Zxc200611 · 2022-03-23 16:28:18 · 题解

Virus synthesis

首先，最后的串一定是一个最后一次翻转得到的回文串在首尾加上一些字符得到的，所以我们最多只能利用原串中的一个回文串。

对原串建出回文自动机。设 s_u 为点 u 所代表的串，dp_u 表示构造 s_u 的最小操作次数，那么答案就是 \min_u |S|-len_u+dp_u。

引理 1：如果要得到一个长度为偶数的回文串 A，那么最后一次操作肯定是翻转。

证明：|A|=2 时，显然先填一个字符然后翻转不劣。

如果 |X| \in [2,l] 时构造 X 的最后一步都是翻转，|A|=|X|+1：

如果最后一次操作不是翻转，找到最后一次翻转出来的回文串 B 所在的位置（如没有翻转操作，那么 |B|=0）。设 |A|=2a,|B|=2b，构造 B 的一半需要操作 d 次。

• 如果翻转前 B 的一半全部位于 A 回文中心的一边：

  绿色是 B 的一半（右边的是翻转前所在的位置）。如果我们用第一种方法，翻转绿色部分得到 B，再在两边填黄色的字符，操作数为 d+1+(2a-2b)。但如果我们用第二种方法，先在绿色部分两边填上黄色字符，再通过一次翻转得到蓝色部分，那么操作数只有 d+(a-b)+1。显然 a \ge b，那么第一种方法不优。

• 如果翻转前 B 的一半跨过了 A 的回文中心：

  串中的粗竖线表示回文中心。

  设一个串 X 的反串为 T(x)，那么有 T(F)=D=T(C)=G=T(H)=E。那么两个串如上，其中黄色和蓝色互为反串、红色和绿色互为反串，设蓝色和黄色长度均为 L_1，构造出一段蓝色需要 d 步，红色和绿色长度均为 L_2。

  如果按照原来的思路，构造出 GC 后翻转得到 DH，添字符得到 EF 与红绿部分，那么需要 d+1+2L_1+2L_2 步。

引理 2：长度为奇数的回文串对于答案没有影响。

证明：长度为奇数的回文串 A 不能由翻转得到，那么找到构造它的过程中最后一次翻转操作翻转出的串 B（如果没有翻转操作那么 |B|=0）。A 的转移全部可以视为由 B 转移得到。

下面只考虑偶回文串。

考虑计算 dp_u。

• 翻转说明这个回文子串必须全部在回文中心的一边，不妨设它在 $s_u$ 的前面一半。 如果这个回文子串不是 $u$ 的前缀，那么在上面的一条转移会被统计到，所以只需考虑 $s_u$ 的回文前缀即可。 设 $u$ 的长度不超过 $\frac{|s_u|}{2}$ 的最长回文前缀所在的点是 $h_u$。

引理 3：这里如果一个回文前缀不是 s_u 的长度不超过 \frac{s_u}{2} 的最长回文前缀 s_{h_u}，那么无需从它转移。

证明：其他长度不超过 \frac{|s_u|}{2} 的回文前缀 X 都是 s_{h_u} 的前缀，X 在后面添加字符得到 s_u 的一半然后翻转得到 s_u。那么添加字符到 h_u 时，由引理 1，我们没有通过翻转得到 s_{h_u}，此时肯定不优，不如通过 s_{h_u} 转移。 那么有转移 dp_u \overset{\min}{\longleftarrow} dp_{h_u}+\left(\frac{|s_u|}{2}-|s_{h_u}|\right)+1。