象形文字 题解

隔壁泞2的如心 · 2024-09-07 18:35:41 · 个人记录

不建议非 IOI 选手来做此题。被影响心态就小丑了，尤其是我自己！！

来先考虑 01 串的情况。首先这个所求子序列一定满足：

• 是两个串的 LCS。

• 0 的数量等于两串 0 数量的较小值，1 也是。

然后如果一个串里 0 和 1 的数量都不大于另一个，那么所求子序列要么是那个短串，要么不存在。

进一步考虑将两串内连续多个 0 记为 [0]，1 也是。那就应该有一个串里 [0] 和 [1] 的数量都不大于另一个，否则一定是 [0][1][0][1][0] 和 [1][0][1][0][1] 的形式，取出公共子序列 1010 和 0101 就寄了。

然后我们设 [0] 与 [1] 较少的串为小串，另一个为大串。这时小串中应有 0 或 1 数量不大于大串，不妨设是 0，这样大串中的 1 不比小串多，不然就被讨论过了。从而小串中的 [0] 会原封不动地到所求字符串里，大串中的 [1] 会拼接后到所求字符串里。

尽管这样，我们好像依然有无穷多种情况要考虑……

• 如果小串为 [0] 或 [1] 的形式，一定合法。

• 如果小串为 [0][1]/[1][0]/[0][1][0] 的形式，那大串应以 [0] 作长到能装下小串的 [0] 的首 / 尾 / 首尾。

• 如果小串为 [1][0][1] 的形式，那么容易发现要么大串也恰好为 [1][0][1] 的形式，要么就在前边已经被讨论过，要么就寄了。

• 其他情况就可以通过调整规约到上述分类里了。

回到原串，那么所求子序列要想存在，至少把任意两种数字提出来视为 01 串也都得满足条件，但这并不充分，至少 111113111211111 和 112211331122 就是个反例。我们可以把所有的数字按照在第一个串出现得是否比在第二个里多分为两类。注意到把两不同类的数字提出来后，要么上下段数相同，要么对应的小串只有一个 [1]，将后者的大串里多余的 0 直接全部删掉，那么在形式上两者就统一了。

所以怎么删掉 0 啊！！！！！！为什么这东西跑我这儿就成了数据结构题了啊！！！！！！

寄！挂！！摆烂！！！爆零！！！！