Yearly Archives

225 Articles

信息学奥林匹克竞赛

Codeforces 1240D: Stack Exterminable Arrays 题解

Posted by kal0rona on

主要思路

刚开始看到分治的标签就下定决心用分治做,没一会发现信息非常难利用就弃疗了。考虑用类似于 KMP 的 AC 自动机的方法完成本题。

首先设置\(dp[i]\)为以\(i\)开头向右延伸的答案,那么我们往左的时候可以合并之,并设置\(nxt[i]\)来进行跳跃;由于得到\(nxt\)数组的过程暴力做时间复杂度会 GG,所以我们可以使用类似 AC 自动机的方式用 Map 合并信息:交换\(nxt[i]+1\)位置的 Map 并设置当前位置。最后做 DP 即可。