洛谷4324 [JSOI2016]扭动的回文串
Luogu 分析 先对每个串跑一遍 Manacher。设求出的分别为 $f_i$ 和 $g_i$。 这时第一、二类的最长长度即为 $\max\left\{f_i\right\}$ 和 $\max\left\{g_i\right\}$。 考虑第三类的最长长度怎么求。枚举中点 $i$，发现此时的扭动串变成了三段：一段是某个串中 $i$ 向外扩展出的回文串，一段是 $A$ 中继续向左扩展出的串，一...
Luogu 分析 先对每个串跑一遍 Manacher。设求出的分别为 $f_i$ 和 $g_i$。 这时第一、二类的最长长度即为 $\max\left\{f_i\right\}$ 和 $\max\left\{g_i\right\}$。 考虑第三类的最长长度怎么求。枚举中点 $i$，发现此时的扭动串变成了三段：一段是某个串中 $i$ 向外扩展出的回文串，一段是 $A$ 中继续向左扩展出的串，一...
Luogu BZOJ 分析 下文中默认字符串的下标从 $0$ 开始。 可以发现答案等于「位置和字符都关于某条对称轴对称的子序列」的数量减去「回文子串」的数量。 后面的就是 manacher 板子，考虑怎么求前面的。 设 $c_i$ 表示「位置和字符都关于对称轴 $i$ 对称的子序列」的数量，则有 后就可以用 FFT 求出 $c_i$ 了。每条对称轴 $i$ 的贡献则为 $2^{c_i}-1...
Luogu LOJ 分析 这个“翻转”操作很容易想到回文。 考虑一个位置怎样才是合法的。可以发现该位置一定满足以下两个条件之一： 回文半径右侧达到 $|S|$ 。 回文半径左侧达到 $1$ ，且右端点合法。 那么只需要用 manacher 求出回文半径，然后从后往前判断就好了。 代码 // =================================== // author: ...