题解 P4987 【回文项链】

command_block

2018-11-08 17:01:37

Solution

[安利Blog](https://www.luogu.org/blog/command-block/) ------------ ### 如此妙 ~~模板~~ 的一道题怎么能没有题解呢? 看到“回文串”,“环”等字眼,直接上**manacher+拆环**乱搞,结果WA,拿了60pts。 后来仔细看了看题面: 我们定义回文串为环上一个**首尾不重叠**的连续子串(即环上每个结点最多被使用一次),且满足存在一个回文中心$i$,使得$i$之前的若干个字符分别与其关于$i$中心对称的字符相同。 对于$100\%$的数据,$n<=10^6$ ,$0<l<=n$**且$l$为奇数**。 ### 只有奇回文串才算数呐! manacher算法没听说过的,右转此题 https://www.luogu.org/problemnew/show/P3805 这题的拆环有些特殊,要把原字符串复制三遍。 不用插‘#’字符跑manacher,然后取**中间那一段**的回文延伸数组和$l$比较。 至于“环上每个结点最多被使用一次”这个要求,**不用理会**(自己想为什么)。 ------------ ~~丑陋的~~ 超短的AC代码。 ```cpp #include<iostream> #include<cstdio> using namespace std int n,k,maxr,p,h[2005000],ans char s[3005000] int main() { scanf("%d%d%s",&n,&k,s+1) for (int i=1 i<=n i++)s[n+n+i]=s[n+i]=s[i] n*=3 for (int i=1 i<=n i++){ if (maxr>i) h[i]=min(maxr-i,p-i+p>0 ? h[p-i+p] : 0) else h[i]=1 while(i+h[i]<=n&&i-h[i]>0&& s[i-h[i]]==s[i+h[i]])h[i]++ if (i+h[i]>maxr){maxr=i+h[i] p=i } }for(int i=n/3+1 i<=n/3*2 i++) if (h[i]*2-1>=k)ans++ printf("%d",ans) return 0 } //分号已删,做了魔改,不影响阅读 //减少代码复制,共建美好洛谷~ ```