题解 CF1394E 【Boboniu and Banknote Collection】

zx2003

2020-10-04 16:25:43

Solution

~~写得过于意识流了。~~ 首先可以验证题面里给出的折叠定义是符合我们直觉的。 对于一个串,我们称其为Z的,当且仅当它能表示为 $A\overline{A}A$。其中 $\overline{A}$ 表示 $A$ 的反转串。 我们称一个非空字符串是本原Z的,当且仅当它是Z的且不包含Z真子串。 性质1:对于一个大串S,如果它的两个偶回文子串满足中心不重叠,且互相包含对方的中心,则该串一定包含一个Z子串。 证明可以考虑以这两个子串的中心为左右端点的子串,将该子串往左右翻转即得一个Z的子串。 推论1:任一本原Z串有唯一的回文前后缀。 性质2:一个大串S如果包含本原Z子串,那么一定存在一种最优方案,使得该子串恰好被沿着唯一的回文前后缀的中心折了两次。 证明的话,由于推论1,讨论一下折叠次数即可。 由性质2,我们可以不断寻找本原Z子串 $A\overline{A}A$ 并将其替换为 $A$。从而我们仅需考虑不包含本原Z子串的串。 子问题:对于一个不包含本原Z子串的串,我们该如何求解? 性质1的推论2:任意一个不包含本原Z子串的串,其任意两个回文后缀的长度之比一定不小于2(大比小)。 于是如果此时答案大于0,则一定存在一次折叠是把原串的某个回文前后缀往里折。 我们暴力枚举这个前后缀并暴力递归,递归状态为区间[l,r]。 看起来状态数是 $O(n^2)$ 的,但实际上,记该串长度为 $n$,最长回文前缀长度为d,可以发现所有出现过的左端点数量大致满足递归式 $T(n)=T(d)+T(n/d)$。 这是因为,首先对于回文后缀的递归不影响左端点数量可以忽略。然后,由推论2,可以认为所有出现过的左端点l被d分为两半,左半边是T(d)。右半边的话,应该可以给T加个角标 $T_d(n)$ 表示头上接了长度为d的回文串后的可能左端点数量,应该可以归纳证明 $T_d(n)=O(\log \frac{n}{d})$。 ~~毛估估一下~~就得到了 $T(n)=O(\log n)$,这也是符合[实验结果](https://codeforces.com/contest/1394/submission/94621407)的。 回到原题,实际上我们额外要做的事是push_back字符的同时维护将所有Z子串消掉的结果。由性质1,一个不包含本原Z子串的串,push_back一个字符后,至多在后缀处产生一个Z子串,删掉即可。 注意到这样得到的所有不包含本原Z子串的串构成一棵Trie,对于Trie上的任一节点执行暴力递归的过程,由前述文字可知到达过的左端点不超过 $O(\log n)$。再加上枚举回文前后缀的过程,总复杂度为 $O(n\log^2n)$。