题解：CF1363F Rotating Substrings

Abczzzzz · 2026-04-25 15:28:38 · 题解

观察到操作其实就是把一个字符往左插，于是无解是好判的，看一下字符出现次数是否相等即可。

考虑 DP。设 f_{i,j} 为 S 长度为 i 的前缀，插入后面若干个字符后，匹配上了 T 长度为 j 的前缀的最少操作次数。（注意定义中 S 串前缀每个字符出现次数一定不超过 T 串前缀）

转移分为三类：

• 添加需求：从后面找值来插入。
• 需求不变：直接匹配。
• 交付需求：那就把需求抵掉。这里可以观察到合法状态一定是可以抵掉的。

最好使用记忆化搜索实现。