本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-15 16:03:30
deepseek翻译官方题解
T2 P12648 [KOI 2024 Round 2] 路灯
“初等部第2题 / 中等部第1题. 路灯” 问题解答
作者：尹教俊
部分问题 1
从 x = 0 到 x = A₁ 的整数位置上的黑暗程度依次是 0, 1, ..., A₁。 此外，从 x = A₁ + 1 到 x = L 的整数位置上的黑暗程度依次是 1, 2, ..., L - A₁。
也就是说，由于排序后的黑暗程度值存在简单的规律，因此可以在比较 A₁ 和 L - A₁ 的大小后输出答案。
部分问题 2
根据题目中给出的公式，可以在 O(N) 时间内计算出一个位置的黑暗程度。
因此，计算所有位置的黑暗程度后进行排序，即可在 O(NL) 的时间复杂度内解决。
部分问题 3
路灯从 0 到 L 等间距分布。
因此，持续输出数字直到输出 K 个数为止：先输出 N 次 0，然后对于 1 及以上的整数，依次各输出 2(N - 1) 次即可。
部分问题 4
观察到以下情况：
- 位置 0 ≤ x ≤ A₁ 的黑暗程度是 A₁ - x。
- 位置 Aᵢ ≤ x ≤ Aᵢ₊₁ 的黑暗程度是 min{x - Aᵢ, Aᵢ₊₁ - x}。
- 位置 A_N ≤ x ≤ L 的黑暗程度是 x - A_N。
对于每个区间，每个位置的黑暗程度可以在 O(1) 时间内计算出来。因此，可以在 O(L) 的时间复杂度内完成所有位置的黑暗程度计算及排序。
部分问题 5
以 N 个路灯的放置位置作为起点进行 BFS。
每当从队列中移除一个（位置，距离）对时，输出的距离值就是题目所要求的答案。
队列的插入和删除操作总共执行 O(N + K) 次。
在将点插入队列之前需要检查其是否已被访问过，这可以使用 std::set 等平衡二叉搜索树库来高效处理。
因此，总时间复杂度为 O((N + K)lg(N + K))。
也可以使用 O(N + K) 的线性时间和空间复杂度来解决此问题。
T3 P12649 [KOI 2024 Round 2] 收集彩球
“初等部第3题 / 中等部第2题. 收集颜色” 问题解答
作者：朴灿率
部分问题 1
由于 N ≤ 2，因此可以预先计算所有可能输入的答案并输出。
部分问题 2
由于 N ≤ 20，因此可以定义 dp[bit] 为状态为 bit 时从初始状态所需的最小移动次数，从而使用位运算的动态规划来解决问题。
将 bit 的第 i 位定义为：如果颜色为 i 的球在同一个箱子中则为 1，否则为 0。由于从每个状态能得出的当前球的箱子分配是唯一的，因此可以使用动态规划。
部分问题 5
设第 i 个箱子中下方球的颜色为 A_i，上方球的颜色为 B_i。考虑一个有 N 个顶点的有向图 G 和一个无向图 G'。对于所有的 A_i, B_i，在 G 中添加有向边 (A_i, B_i)，在 G' 中添加无向边 (A_i, B_i)。如果 A_i = B_i，则在两个图中各添加一条指向自身的边。
在图 G' 中，所有顶点的度数恰好为 2，因此该图由简单环的集合构成。属于不同简单环的顶点互不影响，因此只需逐个处理图中的简单环即可。
如果这样构建的图 G' 中的每个环，在 G 中出度大于等于 2 的顶点不超过 1 个，则可以通过以下过程移动球，使得所有箱子中都装入相同颜色的球：
- 任意选择一个出度小于等于 1 的顶点。
- 将该顶点移动到空箱子中。
- 现在重复以下过程，直到处理完一个环中的所有顶点： – 设刚才选择并移动的顶点为 u。 – 对于所有顶点 v，如果存在边 (v, u) 则将其移除。 – 任意选择一个在 G 中出度为 0 且在 G' 中度数小于等于 1 的顶点 w。 – 顶点 w 的出度为 0 意味着颜色为 w 的球都位于箱子的最顶部。 – 此外，度数为 1 意味着通过一次移动即可将与该颜色相同的球收集到一个箱子中。因此，选择颜色为 w 的两个球中的一个移动到另一个箱子，即可将球收集到一个箱子中。
然而，如果一个环中存在两个或更多出度为 2 的顶点，则无法将上述过程进行到底。否则，将一个环中包含的球移动至每个箱子都装有相同颜色球所需的移动次数如下：
- 设环中包含的顶点数为 V。
- 若 V = 1，则为 0 次。
- 若 V > 1，则为 V + 1 次。
对所有环的上述次数求和，即可求得正确答案。
T4 P12652 [KOI 2024 Round 2] 拔树游戏
“中等部第4题 / 高等部第3题. 树提取” 问题解答
作者：李恩祖
部分问题 1
直接实现题目中给出的操作，可以在 O(N²) 的时间复杂度内解决问题。
部分问题 2
可以证明，在使用管理最小值、最大值的数据结构（如堆）的原理进行提取操作后，对于所有 2 ≤ i ≤ N，A_{P_i} < A_i 仍然成立。因此，根顶点始终是所有顶点中权重最小的。所以答案总是 1, 2, ..., N。
部分问题 3
假设某个顶点 u 有子节点 v₁, ..., v_k，不失一般性地，设 A_{v₁} < ... < A_{v_k}。如果 u 被选为特殊路径，那么具有最小权重的子节点 v₁ 也将被选为特殊路径。根据部分问题的条件，在提取操作之后，顶点 v₁ 的权重会变得更小，因此可知 v₁ 仍然会被选为特殊路径。也就是说，在以 v₁ 为根的子树中的所有顶点都被移除之前，v₁ 会一直被选为特殊路径。即，按照 v₁, ..., v_k 的顺序，这些顶点子树中的所有顶点将依次被选择。因此，从根顶点开始执行 DFS，并按照权重从小到大的顺序访问顶点，即可知 DFS 中的顶点访问顺序就是答案。
部分问题 4
如果只考虑度数为 3 及以上或者是叶子的顶点，可以创建一个压缩形式的树。这样创建的压缩树的边上将挂有一串顶点。对于压缩树中的每个顶点，使用优先队列来管理其相邻顶点的权重，而对于挂在压缩树边上的成串顶点，则使用队列进行管理。根据问题条件，压缩树的高度较小，因此可以在 O(20 log N) 的时间复杂度内找到特殊路径。沿着特殊路径向上移动，同时更新边的队列和顶点的优先队列，则提取操作也可以在 O(20 log N) 的时间复杂度内实现。总时间复杂度为 O(20N log N)。
部分问题 5
通过在子树中解决部分问题，并将其合并来解决父节点的问题。假设某个顶点 u 有子节点 v₁, ..., v_k，将以 v_i 为根的子树对应的答案序列记为 B_{v_i}[...]。这意味着当 v_i 包含在特殊路径中并执行提取操作时，顶点 v_i 的权重按照序列 B_{v_i}[...] 的顺序变化。我们必须利用此信息来找到以 u 为根的子树的答案序列 B_u[...]。显然，B_u[...] 的第一个数字是 A_u。现在，剩余的数字可以通过像执行归并排序一样，从 B_{v₁}[...], ..., B_{v_k}[...] 中选取最小的数字并添加到 B_u[...] 的末尾，重复此过程即可全部求出。
如果简单地实现此过程会导致时间超限，因此需要优化。在从序列 B_i[...] 的前面开始读取时，按照最大值更新的时刻将其划分为新的组的方式来管理组，并将组的代表值定义为该组最左边的数字。例如，序列 2, 1, 3, 5, 4, 8, 6, 7 被管理为 [2, 1], [3], [5, 4], [8, 6, 7]。这样划分组后，在将多个序列合并为一个时，同组的数字将始终保持在同一组中，并且是按照组的代表值顺序进行合并的。此外，代表值比第一个数字小的组将会合并成一个新的组。因此，使用优先队列来管理这些组，并运用"小集合合并到大集合"的技巧，可以在 O(N log² N) 的时间复杂度内解决问题。
再深入思考一下，可以归纳地证明，此解法最终所求的是在保持父-子顺序关系的排列中字典序最小的那个排列。因此，使用优先队列从根顶点开始选择权重最小的顶点，可以在 O(N log N) 的时间复杂度内解决问题。
T5 P12651 [KOI 2024 Round 2] 最大异或
“中等部第3题 / 高等部第2题. XOR最大值” 问题解答
作者：罗正辉
部分问题 1
由于 N ≤ 30，输入规模非常小，因此可以通过检查从 S 中选择 s₁ 和 s₂ 的所有 O(N⁴) 种情况来解决问题。
部分问题 2
介绍两种解法。
解法 1
众所周知，在由 N 个非负整数组成的数组 A 中，选择两个数使其 XOR 值最大化的问题，可以使用 Trie 数据结构在 O(N log(max Aᵢ)) 时间内解决。
本题是从 S 的 O(N²) 个子串中选择 2 个使其 XOR 值最大化的问题，由于每个子串的长度不超过 N，因此可以使用 Trie 在 O(N³) 时间内解决。
解法 2
不失一般性，假设 |s₁| ≥ |s₂|。同时，设 S 中最早出现的 '1' 的位置为 x（索引从 1 开始）。
观察 1： 只需考虑 s₁ 是 S 的前缀的情况。
证明： 假设存在一个答案，其中 s₁ 不是 S 的前缀。如果 s₁ 紧邻的前一个字符是 '1'，则可以将 s₁ 向前扩展一位以增加其值，导致矛盾；如果 s₁ 紧邻的前一个字符是 '0'，则向前扩展一位不会改变答案。因此，如果 s₁ 不是 S 的前缀，可以将其扩展到成为前缀为止。
观察 2： 两个子串 XOR 后，无法得到比从后往前数第 N - x + 1 位更高的位。
证明： 要得到第 t ≥ N - x + 2 位为 1，需要在 S[1···x-1] 之间存在 '1'，但根据 x 的定义，在 S[x] 之前不可能存在 '1'。
观察 3： 只需考虑 s₁ 包含 S[x···N] 的形式。
证明： 需要证明如果 s₁ 不包含 S[x···N]，则无法使第 N - x + 1 位为 1，证明过程与观察 2 类似。
综合以上三个观察，可以得到以下结论：
定理 1： 存在 s₁ = S 的答案。
证明： 根据观察 3，存在 s₁ 是 S 的后缀的答案。又根据观察 1，将 s₁ 向前扩展不会使答案减小。因此，存在 s₁ = S 的答案。
遍历 S 的所有子串 s₂，计算 S 与 s₂ 的 XOR 值并取最大值即可。这种情况下，可能的 s₂ 子串有 O(N²) 个，每次 XOR 操作需要 O(N) 时间。因此，可以在 O(N³) 时间内解决问题。
部分问题 3
介绍两种解法。
解法 1
使用 Trie 优化部分问题 2 的第二种解法，可以在 O(N²) 时间内解决。
解法 2
为方便起见，只考虑 S 中至少出现一个 '0' 和一个 '1' 的情况。如果 S 中没有 '1'，则答案是 0；如果没有 '0'，则答案是将 S 的最后一位改为 '0'。
设 S 中最早出现的 '1' 的位置以及连续的 '1' 的个数为 C，紧接着出现的 '0' 的位置为 P。
观察 4： 存在一个答案，其中 s₂ 的第一个字符与 S = s₁ 的第 P 个字符进行 XOR 运算。
证明： S[P] 是 '0'，并且它的前面（S[P-1]）是 '1'，因此存在方法使得 XOR 结果的第 P 位为 '1'，并且无法在不设置该位为 '1' 的情况下得到更好的答案。此外，容易知道，即使 s₂ 的第一个字符与比 S[P] 更靠前的字符匹配，答案也不会增加。
利用这个观察，可以将 s₂ 的候选数量减少到 C 个。例如，如果 S = 011110ABCDE...，那么 S 与 s₂ 的匹配方式只有以下四种：
S = 011110ABCDE...
s2 = 11110A...
s2 = 1110AB...
s2 = 110ABC...
s2 = 10ABCD...
像这样，s₂ 的候选只有 C(≤ N) 个。实际需要考虑的 s₂ 只有 O(N) 种，因此可以在 O(N²) 时间内求得答案。
部分问题 4
将采用类似部分问题 3 的第二种解法的方式，即寻找与 S[P...N] 进行 XOR 后值最大的 s₂。
给定 A，最大化 A ⊙ B 等价于最小化 notA ⊙ B。寻找这样的 B 的问题，其答案是在所有可能的 B 的候选中，不大于 notA 的最大数，或者不小于 notA 的最小数。因此，如果能在 O(T(N)) 时间内比较子串的字典序，那么除了预处理时间外，可以在 O(N × T(N)) 时间内解决整个问题。
使用字符串 A#notA 的后缀数组，可以在 O(N log N) 时间内完成预处理，并在 O(1) 时间内比较子串的字典序；使用字符串哈希和二分查找，可以在 O(N) 时间内完成预处理，并在 O(log N) 时间内比较子串的字典序。两种方法的总时间复杂度都是 O(N log N)。
部分问题 5
将优化部分问题 3 的第二种解法。假设 S = 011110ABCDE...。
S = 011110ABCDE...
s2 = 11110A...
s2 = 1110AB...
s2 = 110ABC...
s2 = 10ABCD...
如果 A = '1'，则可以确定 s₂ = 10ABCD...；如果 A ≠ '1' 且 B = '1'，则可以确定 s₂ = 110ABC...。
以此类推，设 P 之后首次出现的 '1' 的位置为 P + i，则可以确定 s₂ 是从 P - min(C, i) 位置开始的字符串。因此，可以在 O(N) 时间内找到作为答案的 s₂，从而在 O(N) 时间内解决整个问题。
鲁ICP备2025150228号