P12960 题解

r3winding · 2025-11-04 20:06:29 · 题解

首先我们分析 \text{Bob} 的策略：设 T_0 为空串，对于 1 \le i \le m，\text{Bob} 会将 T_i 重排为字典序 \ge T_{i - 1} 的所有串中，字典序最小的那一个。正确性显然。

考虑如何构造方案：枚举 \text{LCP}(T_i,T_{i - 1}) 的长度，找到最大的长度 x 使得以下条件之一成立：

• 在 T_i 串内，存在一个不属于 \text{LCP}(T_i,T_{i - 1}) 的字符 c，使得 c \gt T_{i - 1, x + 1}。
• 对于当前的 x，T_{i - 1} 串为 T_i 串的非严格前缀(可以有 T_i = T_{i - 1} 的情况)。

直接用桶记录每个元素出现次数即可判定，对于给定的方案我们可以做到 \mathcal{O}(n)。

Subtask #1

因为 m \le 3，所以至多有 \binom{n - 1}{2} 种本质不同的分割方式，我们考虑直接枚举这些分隔点，对每种情况模拟 \text{Bob} 的最优策略即可，时间复杂度 \mathcal{O}(n^3)。

值得一提的是，当 m = 2 时我们可以在线性时间复杂度内解决这个问题。只需要从左往右移动唯一的分割点，对左侧 T_1 和右侧 T_2 分别开一个桶维护每种字符出现次数。移动一次分界点只会在左侧的桶中假如一个元素、在右侧的桶中删除一个元素，修改/判定都是 \mathcal{O}(1) 的，因此总时间复杂度可以做到 \mathcal{O}(n)。

Subtask #2

由上一个子任务我们已经可以解决 m = 2 的情况。

对于 m = n 的情况，每个子串都只有一个字符，\text{Bob} 无法有效重排任何一个子串，所以只需要比较原串相邻字符的字典序即可在 \mathcal{O}(n) 时间复杂度内解决问题。

对于 m \ge 4 的情况，我们发现对 \text{Alice} 的限制是松的，考虑找出能使 \text{Alice} 必胜的最小子结构：

• 如果 s 不是有序字符串，\text{Alice} 可以直接选取第一对相邻的 s_i \gt s_{i + 1}，直接将它们拆成 T_j = s_i,T_{j + 1} = s_{i + 1}，此时必定有 T_j \gt T_{j + 1}，那么 \text{Bob} 必不可能获胜。
• 否则，如果 s 中出现了连续 3 个(及以上)的相同字符 s_{i - 1} = s_{i} = s_{i + 1}，那么直接拆成 T_j = s_{i-1}+s_i,T_{j + 1} = s_{i+1}，那么此时必定有 T_j \gt T_{j+1}，\text{Bob} 同样必败。
• 否则，\text{Alice} 显然必败，归纳法不难证明。

仅剩 m=3 的最困难情况尚未解决。假设 \text{Alice} 将字符串 s 拆分为三部分 A,B,C（即 s=ABC）。显然：

1. 若以 m=2 对应构造方式分割子串 AB 结果为 A,B 时 \text{Alice} 获胜，则 A,B,C 构成 m=3 下输入串 s=ABC 的有效分割方案。
2. 若以 m=2 对应构造方式分割子串 BC 结果为 B,C 时 \text{Alice} 获胜，则 A,B,C 同样构成 m=3 下输入串 s=ABC 的有效方案。

一个结论是：对任意字符串 s，\text{Alice} 获胜当且仅当上述两种情况之一成立。这并非显而易见：存在有效分割 A,B,C 既不满足 AB 分割有效也不满足 BC 分割有效的反例，例如输入串 XYAZXY 的分割 XY/AZ/XY。但在所有此类情形中，必然存在满足条件的其他有效分割方案。

以 XYAZXY 为例，XY/A/ZXY 即为有效分割（因 XY/A 满足 m=2 的获胜条件）。证法和 m \ge 4 类似，同样考虑最小子结构，如果不能单独成段必定无解，否则所有有解情况和最小拆分情况必定一一对应。

最终，我们只需检验 \text{Alice} 能否在 m=2 条件下赢得 s 的某个前缀或后缀。总时间复杂度 \mathcal{O}(n)。