题解：P15650 [省选联考 2026] 摩卡串 / string

· · 题解

省流：复杂度 O(nk^{1.5})。

考虑特殊性质，发现都是 DP。

于是我们认为正解也是 DP。

考虑从前向后放字符。

我们发现一些位置开头的前缀在某一次被认为小后之后都在贡献。

然后这些在这之前都是 s 的一段前缀。

考虑 dp_{k,len,c,0/1} 表示已经有 k 个符合要求，当前串最多能匹配到 s 长为 len 的前缀，有 c 个开头位置之后都在贡献，是否存在子串 s 时，n 最小值。

发现当 len 确定，对自己和 k,c,0/1 影响就确定了，先预处理，然后转移即可。

复杂度 $O(nk^2)$。 不过似乎 $c$ 很大的时候走不了几步。 我们有理由怀疑甚至 $c$ 还没成长起来 $k$ 就爆了。 考虑我们尽量快增加 $c$，单次最多增加 $len$，最后 $c$ 只需要开到 $10^3$。 空间还是爆的。 考虑发现每次 $c$ 增长都伴随 $len$ 的减少。 于是经过分析，发现 $c$ 最多开到 $O(k^{0.5})$。 具体就是先把 $len$ 开满后 $c$ 逐渐增加，每次增加 $1$，每次都对 $k$ 贡献。 于是复杂度 $O(nk^{1.5})$。