专栏文章

P12960 题解

rr3winding
P12960题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mindp41b
此快照首次捕获于
2025/12/02 00:43
3 个月前
此快照最后确认于
2025/12/02 00:43
3 个月前
查看原文
首先我们分析 Bob\text{Bob} 的策略：设 T0T_0 为空串，对于 1≤i≤m1 \le i \le m，Bob\text{Bob} 会将 TiT_i 重排为字典序 ≥\ge Ti−1T_{i - 1} 的所有串中，字典序最小的那一个。正确性显然。
考虑如何构造方案：枚举 LCP(Ti,Ti−1)\text{LCP}(T_i,T_{i - 1}) 的长度，找到最大的长度 xx 使得以下条件之一成立：
  • 在 TiT_i 串内，存在一个不属于 LCP(Ti,Ti−1)\text{LCP}(T_i,T_{i - 1}) 的字符 cc，使得 c>Ti−1,x+1c \gt T_{i - 1, x + 1}。
  • 对于当前的 xx，Ti−1T_{i - 1} 串为 TiT_i 串的非严格前缀(可以有 Ti=Ti−1T_i = T_{i - 1} 的情况)。
直接用桶记录每个元素出现次数即可判定，对于给定的方案我们可以做到 O(n)\mathcal{O}(n)。

Subtask #1

因为 m≤3m \le 3，所以至多有 (n−12)\binom{n - 1}{2} 种本质不同的分割方式，我们考虑直接枚举这些分隔点，对每种情况模拟 Bob\text{Bob} 的最优策略即可，时间复杂度 O(n3)\mathcal{O}(n^3)。
值得一提的是，当 m=2m = 2 时我们可以在线性时间复杂度内解决这个问题。只需要从左往右移动唯一的分割点，对左侧 T1T_1 和右侧 T2T_2 分别开一个桶维护每种字符出现次数。移动一次分界点只会在左侧的桶中假如一个元素、在右侧的桶中删除一个元素，修改/判定都是 O(1)\mathcal{O}(1) 的，因此总时间复杂度可以做到 O(n)\mathcal{O}(n)。

Subtask #2

由上一个子任务我们已经可以解决 m=2m = 2 的情况。
对于 m=nm = n 的情况，每个子串都只有一个字符，Bob\text{Bob} 无法有效重排任何一个子串，所以只需要比较原串相邻字符的字典序即可在 O(n)\mathcal{O}(n) 时间复杂度内解决问题。
对于 m≥4m \ge 4 的情况，我们发现对 Alice\text{Alice} 的限制是松的，考虑找出能使 Alice\text{Alice} 必胜的最小子结构：
  • 如果 ss 不是有序字符串，Alice\text{Alice} 可以直接选取第一对相邻的 si>si+1s_i \gt s_{i + 1}，直接将它们拆成 Tj=si,Tj+1=si+1T_j = s_i,T_{j + 1} = s_{i + 1}，此时必定有 Tj>Tj+1T_j \gt T_{j + 1}，那么 Bob\text{Bob} 必不可能获胜。
  • 否则，如果 ss 中出现了连续 33 个(及以上)的相同字符 si−1=si=si+1s_{i - 1} = s_{i} = s_{i + 1}，那么直接拆成 Tj=si−1+si,Tj+1=si+1T_j = s_{i-1}+s_i,T_{j + 1} = s_{i+1}，那么此时必定有 Tj>Tj+1T_j \gt T_{j+1}，Bob\text{Bob} 同样必败。
  • 否则，Alice\text{Alice} 显然必败，归纳法不难证明。
仅剩 m=3m=3 的最困难情况尚未解决。假设 Alice\text{Alice} 将字符串 ss 拆分为三部分 A,B,CA,B,C（即 s=ABCs=ABC）。显然：
  1. 若以 m=2m=2 对应构造方式分割子串 ABAB 结果为 A,BA,B 时 Alice\text{Alice} 获胜，则 A,B,CA,B,C 构成 m=3m=3 下输入串 s=ABCs=ABC 的有效分割方案。
  2. 若以 m=2m=2 对应构造方式分割子串 BCBC 结果为 B,CB,C 时 Alice\text{Alice} 获胜，则 A,B,CA,B,C 同样构成 m=3m=3 下输入串 s=ABCs=ABC 的有效方案。
一个结论是：对任意字符串 ss，Alice\text{Alice} 获胜当且仅当上述两种情况之一成立。这并非显而易见：存在有效分割 A,B,CA,B,C 既不满足 ABAB 分割有效也不满足 BCBC 分割有效的反例，例如输入串 XYAZXY 的分割 XY/AZ/XY。但在所有此类情形中，必然存在满足条件的其他有效分割方案。
以 XYAZXY 为例，XY/A/ZXY 即为有效分割（因 XY/A 满足 m=2m=2 的获胜条件）。证法和 m≥4m \ge 4 类似，同样考虑最小子结构，如果不能单独成段必定无解，否则所有有解情况和最小拆分情况必定一一对应。
最终，我们只需检验 Alice\text{Alice} 能否在 m=2m=2 条件下赢得 ss 的某个前缀或后缀。总时间复杂度 O(n)\mathcal{O}(n)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...