CF1789F Serval and Brain Power 题解报告。

Cocoly1990 · 2023-02-26 20:37:02 · 题解

记 k 为循环节个数。

• 当 k 为偶数时：发现可以简单的用 k=2 代替，枚举分界点并对左右边做 LCS，答案为 LCS 长度的两倍。

• 当 k 为奇数时，这时候不一定有简单的代替方法了，所以进一步分类讨论：

  • 当 k=3 时，枚举两个分界点并做三元 LCS，复杂度 \mathcal{O}(n^5)，你以为他跑不过去，其实他带着 \frac{1}{27} 的常数。
  • 当 k=5 时，不难发现 \frac{80}{5}=16，其实已经很小了。这时候发现最后的作为周期的串一定可以在连续 16 个字符内找到，因此对于每连续 16 个字符，枚举每个字符选或者不选，在回到原串 check 一次，复杂度 \mathcal{O}(n^2\times 2^{16})。

然后就做完了？综合时间复杂度 \mathcal{O}(n^3+n^5+n^2\times 2^{16})。