AGC046D 题解

OtoriEmu · 2023-02-22 22:35:09 · 题解

竟然是能自己做出来的题。

显然不能对在删除的数选一个插入到原字符串这个操作进行描述。我们考虑将插回的这个数放到一个集合中，之后如果要删到它就直接在集合内删掉它即可。

这样若干次操作之后，剩下的东西有原字符串的一个后缀，还有若干个集合内的 0 和 1。用三元组 (i,j,k) 描述：原字符串剩下 s[i+1 \dots n] 这部分，集合内有 j 个 0 和 k 个 1。三元组的个数显然是 O(n^3) 的。

那么算出所有合法的三元组。具体的采用 DP，定义 g_{i,j,k} 表示三元 (i,j,k) 是否合法。转移可以删除两个集合内的数留下一个，删除一个集合内的数和 a_{i+1} 留下一个，删除 a_{i+1},a_{i+2} 留下一个。具体实现查看代码。

接下来要算有多少个可生成的字符串对应合法的三元组。注意到一个字符串可以对应上很多个三元组，我们需要使一个字符串对应的三元组唯一。可以采取这样的手段：从后往前放字符，当前字符串匹配上了 s[i\dots n]，需要多插入 j 个 0，k 个 1。分放 0 还是 1 讨论。这样就可以使每个字符串对应的三元组相同（(i,j,k) 对应的三元组是 (i-1,j,k)）。

这个可以采取 DP 转移，f_{i,j,k} 就表示当前用 (i,j,k) 描述的字符串数量，分放什么字符讨论即可。

评测记录。