题解：P9753 [CSP-S 2023] 消消乐【哈希，DP】

chenwenmo · 2025-10-25 00:54:23 · 题解

P9753 [CSP-S 2023] 消消乐

做法一：哈希 + 栈

考虑用栈来刻画合法子串。

枚举起始点，用栈扫一遍，记录出现了几次空栈，即可做到 O(n^2)，50 pts。

考虑优化，尝试能否只扫一遍就计算出答案。

假设当前栈状态为 s，然后让 s 按顺序接受一个合法串 t，看一下接受后的 s 是什么样的，

• 当 |t|=2，显然 s 不变。
• 当 |t|>2 时，归纳假设：任意长度 <|t| 的合法串的入栈都不会使 s 改变。
  • 当 t=c_1+a+c_2，其中 c_1 和 c_2 为两个相等的字符，a 为任意合法串。
  • 当 t=b_1+b_2+\cdots+b_k 时，其中 b_i 为任意合法串。显然 s 不变。

综上所述，s 接受一个合法串后不会改变状态。

那么反过来归纳一下，假设任意长度 <|t| 且不会改变 s 的串一定是合法串，

• - 显然 $t$ 一定存在相邻两个相等的字符。 - 把 $t$ 中任意两个相邻相等的字符删去得到 $t'$，$t'$ 的能使栈状态不变，根据归纳假设，$t'$ 是合法串。 - 显然在合法串任意位置中加入两个相邻相等的字符后还是合法串。

于是可证这个条件是充要的。也就是说，我们从 1 扫到 n 时，对于两个位置的状态相等的栈，中间一定存在一个合法子串。

于是我们 哈希 + map 记录扫到每个位置时栈的状态即可，复杂度 O(n\log n)。单模哈希被卡了，笔者写了双模哈希。

Code

做法二：DP

设 f(i) 表示以 i 结尾的合法子串个数，这个比较容易想到。

考虑转移，f(i)\gets f(g(i)-1)+1。g(i) 表示最大的 j<i，使得 [j,i] 是合法子串。

考虑如何求出 g(i)，令 x=i-1，若 x>0 就不断使 x\gets g(x)-1，直到 s[x]=s[i]，这时 g(i)=x。正确性显然。接下来证明这样跳的复杂度为 O(n|\Sigma|)。参考证明

• 设 j>i，且以 x=j-1 为起始点，不断跳到 g(x)-1，能跳到 i。
• 反证法。假设存在 k>j，使得 s[k]=s[j]，且 k 能跳到 i。
• 显然 s[i+1,j-1] 和 s[i+1,k-1] 都是合法串。
• 根据 做法一 中证明的结论，可以发现 s[j,k-1] 是合法串。
• 因此一定存在 t\in[j+1,k-1]，使得 s[t]=s[j]，且在合法串 s[j,k-1] 中，t 和 j 是匹配的。
• 因此 s[j,t] 是合法串。
• 因此 s[t+1,k-1] 是合法串。
• 又因为 s[t]=s[j]=s[k]，于是 k 最多跳到 t 就会停止，不会跳到 i。假设不成立。
• 综上所述，每个点最多会被每种颜色中的一个点跳到，故复杂度为 O(n|\Sigma|)。

Code

通过简单处理即可做到 O(n)。Code