洛谷4324 [JSOI2016]扭动的回文串
Luogu分析先对每个串跑一遍 Manacher。设求出的分别为 $f_i$ 和 $g_i$。这时第一、二类的最长长度即为 $\max\left\{f_i\right\}$ 和 $\max\left\{g_i\right\}$。考虑第三类的最长长度怎么求。枚举中点 $i$，发现此时的扭动串变成了三段：一段是某个串中 $i$ 向外扩展出的回文串，一段是 $A$ 中继续向左扩展出的串，一段是 $...
标签 Manacher 下的文章
- 首页
- Manacher
BZOJ5036 [Jsoi2014]回文串
BZOJ分析首先在每两个字符中插入 texttt{#}，然后跑 Manacher。记 Manacher 求出的数组为 $f$。考虑每个询问。我们首先扩展到插入 texttt{#} 后的串，即令 $l\leftarrow 2\times l-1$，$r\leftarrow 2\times r+1$。设新串中的答案为 $ans'$，则原答案为 $\frac{ans'-(r-l+2)}{2}$，意...
洛谷4199 万径人踪灭
LuoguBZOJ分析下文中默认字符串的下标从 $0$ 开始。可以发现答案等于「位置和字符都关于某条对称轴对称的子序列」的数量减去「回文子串」的数量。后面的就是 manacher 板子，考虑怎么求前面的。设 $c_i$ 表示「位置和字符都关于对称轴 $i$ 对称的子序列」的数量，则有后就可以用 FFT 求出 $c_i$ 了。每条对称轴 $i$ 的贡献则为 $2^{c_i}-1$，累加起来即可...
洛谷5446 [THUPC2018]绿绿和串串
LuoguLOJ分析这个“翻转”操作很容易想到回文。考虑一个位置怎样才是合法的。可以发现该位置一定满足以下两个条件之一：回文半径右侧达到 $|S|$ 。回文半径左侧达到 $1$ ，且右端点合法。那么只需要用 manacher 求出回文半径，然后从后往前判断就好了。代码// =================================== // author: M_sea // ...
洛谷4555 [国家集训队]最长双回文串
LuoguBZOJ分析$\mathrm{manacher}$ 。处理出两个数组 $L[i]$ 和 $R[i]$ ，分别表示以 $i$ 为开头/结尾的最长回文串长度。显然可以在跑完 $\mathrm{manacher}$ 后 $O(n)$ 得出。然后直接扫一遍求出 $\max\{L[i]+R[i]\}$ 就行了。需要注意的是，这里的 $L[i]$ 和 $R[i]$ 都不能为 $0$ 否则你会在...
洛谷1659 [国家集训队]拉拉队排练
LuoguBZOJ分析$\mathrm{manacher}$ 。先求出以每个数为中心的回文串长度。因为只关心奇数长度的串，所以没必要补#。然后考虑怎么统计答案。设 $o[i]$ 表示长度为 $i$ 的回文串的个数。因为长度为 $i$ 的回文串包含了长度为 $j\;(j<i)$ 的回文串，所以可以先把每个长度加进去，再求一遍后缀和。算答案就很简单，直接扫一遍，然后用快速幂计算就行了。具体...
洛谷3454 [POI2007]OSI-Axes of Symmetry
LuoguBZOJ分析把每条边的长度和每个角的大小按顺序排列，可以组成一个环。把这个环在某条对称轴的地方断开，形成的串显然是回文的。于是把这个环倍长，然后长度 $> len$ 的回文串个数就是答案（这里的 $len$ 是环长）。直接跑 $\mathrm{manacher}$ 即可。具体的，长度可以不开根号，角的大小可以用叉积。然后最后的答案要 $/2$ ，因为每条对称轴被算了两次。具...