P9753 [CSP-S 2023] 消消乐

5ab_juruo · 2023-10-22 22:01:24 · 个人记录

对于一个合法的串 S，设其最后一对被消的字符为 a，则 S 必然可以被分割成 T_1aT_2aT_3 的形式，其中 T_1,T_2,T_3 都是合法串。递归下去，即所有合法串都可以像括号序列一样地被定义，即：

• 一对字符 aa 是合法串；
• 若 S 是合法串，则 aSa 也是合法串；
• 若 S,T 是合法串，则 ST 也是合法串。

接下来我们将区分左括号的字符和右括号的字符。我们维护一个栈存所有当前的左括号的字符，但如果栈中有两个相邻的相同字符会很难受，所以我们要把这种情况调整掉。

具体而言，设有两个 a_( 在合法串 S 的栈中相邻，则 S=a_(T_1a_(T_2a_)T_3a_)，根据定义 T_1,T_2,T_3 均为合法串。此时将其调整为 a_(T_1a_)T_2a_(T_3a_) 也合法，且这样的调整必然是有限的。

所以可以得到合法串的判定：维护一个栈，若当前字符和栈顶相同就 pop，否则就 push，若最后栈可以删空即合法。

对于子串问题，我们断言，若 l 时刻后的栈形态和 r 以后的栈形态一致，则 (l,r] 子串即为合法串。依旧是考虑递归证明：

• 若 (l,r) 中还有其他位置栈形态与两端一致的，则分段处理，最后将每一段的串顺次拼接。
• 否则，考虑 l+1,r-1 的栈形态，我们断言其必须相同，否则：
  • 若 l+1,r-1 栈大小不一致，则中间必然有一个状态要返回和 l,r 一样大小的栈，与假设矛盾；
  • 若 l+1,r 加入的字符不一致，则中间必然有一个状态要删除 l+1 插入的字符，回到 l 形态的栈，与假设矛盾。
• 即 l+1,r 必然同时删除，或加入相同的字符。

按照合法串定义，(l,r] 必然为一个合法串。

还要证个方向，考虑按照定义递归易证。