Codeforces Round 914 (Div. 2)
内容提要
本文解析 Codeforces Round 914 Div.2 四道题：A 题枚举骑士 8 个落点，统计同时攻击国王与皇后的位置数；B 题排序后求前缀和，计算每个值最多可消除的元素数；C 题因三次操作可得 0，只需考虑 0、1、2 次操作，暴力枚举差值并查找最接近值；D2 题用单调栈求各值的最大作用区间，再用双指针验证数组 a 能否变为 b。
延伸解读
题目难度与算法分布
本场 Div.2 的四道题覆盖了从暴力枚举到单调栈、双指针等不同难度的算法。A 题和 B 题侧重基础实现与排序前缀和，适合快速上手；C 题需要发现操作三次可得 0 的关键性质，将问题简化；D2 题则结合单调栈求作用区间和双指针验证，对思维和代码能力要求较高。整体难度梯度明显，适合不同水平的选手练习。
C 题的关键观察与简化
C 题允许每次将两个数的差值加入数组，问 k 次操作后数组最小值的最小可能。文章指出，若操作三次，可以连续两次取同两个值的差值，再将结果差值加入，必然得到 0。因此只需考虑 k=0、1、2 的情况。这种利用操作次数上限来简化分类讨论的思路，是解决此类构造问题的常见技巧。
D2 题的实现要点
D2 题要求判断能否通过区间取最大操作将数组 a 变为 b。文章使用两次单调栈分别求出每个 a[i] 向左和向右能扩展的最大区间，确保区间内没有比 a[i] 更大的值。随后用双指针从右向左匹配 b 中的每个值，检查是否存在一个 a 中的值等于 b[i] 且其作用区间覆盖当前位置。这种预处理加验证的方法有效降低了复杂度。
Q&A
Codeforces Round 914 Div.2 的 A 题 Forked! 应该怎么解？
暴力枚举骑士的 8 个可能落点，统计同时攻击国王和皇后的位置数。具体做法：用集合存储骑士从国王位置出发能到达的所有位置，然后检查从皇后位置出发能到达的位置是否在集合中，计数即可。
B 题 Collecting Game 中，如何计算每个初始值最多能消除多少元素？
将数组排序并求前缀和。对于每个值，如果当前和大于等于下一个值，则可以继续消除并累加；最终结果卡在某个位置，使得所有比它小的值之和小于它。用双指针或类似前缀和的方法处理，得到每个位置能消除到的最大索引。
C 题 Array Game 中，当操作次数 k 大于等于 3 时，为什么答案一定是 0？
因为可以通过三次操作得到 0：先选两个值得到差值，再选同样的两个值得到相同差值，最后将两个差值相减得到 0。所以 k>=3 时最小值必为 0。
D2 题 Set To Max (Hard Version) 如何判断数组 a 能否变成数组 b？
先用单调栈求出数组 a 中每个值的最大作用区间 [la, ra]（即该值能作为区间最大值的范围）。然后用双指针从右向左匹配：对于每个 b[i]，在 a 中找到一个值等于 b[i] 且其作用区间包含 i，若找不到则输出 NO，否则 YES。
C 题 Array Game 中，k=1 和 k=2 时分别如何计算最小可能值？
k=1 时，暴力枚举所有数对，计算差值，取最小差值与原数组最小值中的较小者。k=2 时，同样枚举数对得到差值，然后在原数组中用二分查找找到最接近该差值的元素，更新最小值。
B 题 Collecting Game 中，为什么排序后可以用前缀和来解决问题？
因为每个值可以消除所有小于等于它的值，并且消除后当前值会增加。排序后，如果当前累积和大于等于下一个值，就可以继续消除并累加。最终会卡在某个位置，使得累积和小于下一个值，此时能消除的元素个数就是当前位置的索引。
