BZOJ 3790 神奇项链


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3790

题意:有两个机器,第一个可以制作任意回文串,第二个可以拼接两个回文串,并且可以去掉前后缀的重叠部分,问得到给定串的最少二机器使用次数。


考虑处理出每个下标 i 向右最长延伸的回文串长度\(r_i\),即用一些线段可重的覆盖线段。

这个过程 \(O(n)\) 的贪心即可,在满足左端点的情况下右端点越远越好。

对于处理 \(r_i\) 数组,可以用回文自动机,即在每次插入一个字符后用 \(len_{last}\) 去更新 \(r_{n-len[last]+1}\)。

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 3790 神奇项链


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,