P9753 [CSP-S 2023] 消消乐 题解

· · 题解

主要写写暴力跳做法的复杂度证明。

做法简述：

求以每个点为结尾的极短可消段，记其左端点为 f_i，先设 f_i=i-1，然后跳 f_i=f_{f_i}-1，直到 s_{f_i}=s_i。再设 g_i 表示以 i 为结尾，可消段数量，g_i=g_{f_i-1}+1。ans=\sum g_i。

复杂度证明：

aabbcc...zzaabbcc...zzaabbcc... 这样的串可以把这个做法卡成 \frac 12n\Sigma，所以复杂度显然大于 O(n)。

考虑分析一个点 i 能被哪些点跳到。猜测同一个颜色只能有一个点 j 跳到 i。

假设存在 k>j,s_k=s_j，k 能跳到 i，
因为跳的是极短可消串，所以此时 [i+1,j-1] 和 [i+1,k-1] 都是可消串，若 i+1=j 也不影响后面的结论。

$\therefore\exist t\in(j,k),s_t=s_j$，满足从 $j$ 开始扫到 $t$ 时 $j$ 可以被删掉， $\therefore [j,t]$ 是可消串， 此时若 $t$ 恰等于 $k-1$ ,那么 $k$ 显然跳到 $t$ 时就停了，不可能跳到 $i$，无需考虑。 否则 $[t+1,k-1]$ 可消， $\because s_t=s_j=s_k$， $\therefore f_k\ge t>j>i$，$k$ 无法跳到 $i$。 与假设矛盾，所以不存在 $k>j,s_k=s_j$，$k$ 能跳到 $i$， 所以每个点最多被 $\Sigma=26$ 个位置跳到。复杂度为 $O(n\Sigma)$。