3月CF杂题

Codeforces Round 853 (Div. 2)

打的 VP 。

E. Serval and Music Game

妙妙题。

F. Serval and Brain Power

妙妙题 +1 。

对 \(k\ge5\) 的情况，我们把整个序列分成 5 段，那么 T 一定是至少一段的子序列（不懂可以手玩一下）。枚举每一段的子序列，查找 S 内包含个数，时间复杂度 \(\text{O}(5\times2^{\frac{|S|}{5}}\times|S|)\) 。

对于 \(k<5\) 的情况，我们只用考虑 k=2 或 k=3 （因为 k=4 包含在 k=2 里面）。枚举断点把 S 分成 k 段，对 k 段求 LCS 即可。 k=3 时时间复杂度为 \(\text{O}(|S|^{5})\) 。