P10215 [CTS2024] 字符串游戏

· · 题解

P10215 [CTS2024] 字符串游戏

翻转字符串，每次删去 s[l, r] 并获得其在 s[1, r] 中的出现次数作为分数，记为 occ(l, r)，则有简单 DP：设 f_i 表示 s[1, i] 的答案，则 f_i = \max_{j = 0} ^ {i - 1} (occ(j + 1, i) - f_j)。

容易做到 \mathcal{O}(n ^ 2)：建出 SAM，转移 f_i 前加入 s[1, i] 的所有后缀，即从 s[1, i] 对应的结点开始在 link 树上跳父亲，并将经过结点的 occ 值加 1，\mathcal{O}(1) 求 occ(p, i)。通过 dfs 序拍平换成 BIT，则修改和查询均为 \mathcal{O}(\log n)。

首先有个很显然的性质，对 $q < p$，$occ(q, i) < occ(p, i)$。于是如果 $f_p < f_q$，那么 $p$ 一定更优。因此只需保留 $f$ 递增的单调栈上的转移点。 此外还有 $occ(p, i) \geq occ(p, i + 1)$，也很容易理解，因为 $s[p, i + 1]$ 出现的位置一定也有 $s[p, i]$ 出现。这个性质在算法三、四时需要用到。 充分发挥人类智慧，每次只取单调栈上的前 $20$ 个和后 $20$ 个转移，无法通过。思考一下什么时候这样做会寄掉。打表观察发现，当字符串形如若干个 $\texttt {aaa...ab}$ 拼接时，对较大的 $i$，若 $s_i = \texttt b$，则策略为选择一整个 $\texttt {aaa…ab}$ 循环节，但该决策点在单调栈中间，导致不能正确转移。 **做法一** 继续打出寄掉时单调栈的信息，发现决策点与其下一个位置的 $occ$ 相差不大，但 $f$ 值相差非常大，根本不是同一个数量级：决策点的位置是前一个 $\texttt b$，且对 $s_i = \texttt a$，$f_i = \mathcal{O}(i)$，但对 $s_i = \texttt b$，$f_i = \mathcal{O}(\frac i {L})$，其中 $L$ 是循环节长度。 基于打表观察得出的信息，我们再次充分发挥人类智慧，认为对于单调栈上的相邻两个位置 $p, q$，只有当 $f_p \cdot c < f_q$ 时，$p$ 才会作为转移点，其中 $c$ 是一个大于且接近 $1$ 的常数，$c = 1$ 即普通单调栈。经测试，取 $c = [1.05, 2]$ 均可通过，$c$ 较小时常数过大，$c$ 较大时不能保证正确性。 时间复杂度 $\mathcal{O}(n\log ^ 2n)$，正确性未知，但是比 std 快。 **做法二** 从出题人角度思考，一定会造出大循环串套小循环串卡掉这种做法。循环串会导致单调栈上一段区间的 $f$ 形成等差数列，大胆猜测根据某种神秘的单调性，只保留等差数列的两端是正确的，或者说，很难卡掉正确性。但是转移点数量依然为 $\mathcal{O}(n)$。 既然只保留一条直线的两端是可行的（指可以通过本题测试数据的正确性验证，并非结论），考虑到斜率会下降，我们不妨更大胆一些，只保留凸包上的点（每个点的横坐标是它在单调栈上的位置，不是在原序列的位置，很幽默）。虽然转移点数量为 $\mathcal{O}(\sqrt n)$，不仅时间复杂度不对，正确性也没有保证，但它就是通过了，而且比 std 快。 **做法三** 一个不那么明显的观察是，对 $q < p$，当 $i\to i + 1$ 时，$occ(q, i)$ 减小的量不大于 $occ(p, i)$ 减小的量。因为 $s[q, i]$ 出现的地方 $s[p, i]$ 一定出现，而 $s[q, i + 1]$ 相较于 $s[q, i]$ 少出现的地方，$s[p, i + 1]$ 也一定相对应地相较于 $s[p, i]$ 少出现了。 于是一个位置会被它之前的位置反超，这是另类决策单调性，使用二分栈解决，时间复杂度 $\mathcal{O}(n\log ^ 2n)$。需在线计算 $occ$，需要可持久化线段树，常数过大导致无法通过。 **做法四** 考虑所有没有被 $i$ 弹出的单调栈上的位置，设最后一个这样的位置为 $p$，则 $f_p < f_i$。对 $q < p$，若 $q$ 是 $i$ 的决策点，则 $$ f_p \geq occ(q + 1, p) - f_q \geq occ(q + 1, i) - f_q = f_i > f_p $$ 矛盾。这说明每次只需用栈顶位置 $p$ 更新 $f_i$，若 $f_p \geq f_i$ 则弹出，否则退出。 时间复杂度 $\mathcal{O}(n\log n)$。需要倍增定位子串，这也是做法一、二比做法四更快的原因。