2026.4 做题记录

复健，举步维艰啊．

Codeforces 2217C Grid Covering

$n$ 或 $m$ 小于 2 的情况可以讨论掉，以下分析默认 $n, m \ge 2$．

能遍历所有格子的一个必要条件是，每个格子的 $x$ 和 $y$ 坐标都能被取到，容易发现这个等价于 $n$ 与 $a$ 互质且 $m$ 与 $b$ 互质．

考虑一个简化的情况．我们将一次 $x$ 方向移动和一次 $y$ 方向移动称作一组移动，考察整数组移动能到达的格子．由上述的分析可得，$x$ 坐标的周期是 $n$，$y$ 坐标的周期是 $m$，容易知道坐标序列 $(x, y)$ 的周期是 $\mathrm{lcm}(n, m)$．那么当 $\gcd(n, m) = 1$ 时，仅仅考虑整数组移动，$x$ 和 $y$ 坐标的组合就可以取遍所有情况，这显然是合法的．

接下来考虑 $\gcd(n, m) \not= 1$ 的情况．若能遍历所有格子，能到达的状态数至少要是 $nm$．但能对状态进行贡献的，只有整数组移动和在其基础上某个方向多一次移动构造出的坐标序列，能构造出的状态数至多只有 $2 \mathrm{lcm}(n, m)$．若 $\gcd(n, m) > 2$，那么总状态数不可能大于 $nm$．故只用讨论 $\gcd(n, m) = 2$ 的情况．

容易发现只有在两种方式构造出的坐标序列中有元素相同时，能构造出的状态数小于 $nm$．考察何时两个序列中有元素相同，不妨令 $y$ 方向上多一次移动，可以构造出下列同余方程 $sa \equiv ta \pmod n, sb \equiv (t+ 1) b \pmod m$，即 $s - t \equiv 0 \pmod n, s - t \equiv 1 \pmod m$．即存在整数 $p, q$ 使得 $s - t = pn = qm + 1$，即 $pn - qm = 1$．由 Bézout 定理，这不可能成立，故两个序列中的元素两两不同，总状态数为 $nm$．故 $\gcd(n, m) = 2$ 的情况总是合法．

Codeforces 2217D Flip the Bit

可以发现，特殊位置划分出的连续段之间操作相对独立．或者说，我们在尝试抹平一个连续段的时候可以不对其他连续段造成影响．

考虑利用 Easy Version 中的方式计算出每个连续段被抹平需要的操作数．由于最终要求和特殊位置的初始值相同，可以发现我们从每个连续段的左边或者右边开始操作，所需的总操作数是一致的．

对于一个特殊位置，我们可以选择一个从它左边的连续段开始，到它右边的连续段结束的区间，进行一次操作．这可以同时扣除两个连续段的待操作数．若我们已经将一个连续段抹平，我们可以将其两端的特殊位置看做一个，进行类似上述的操作．

我们可以用一个更直观的方式来看这个过程：令第 $i$ 个连续段的待操作数是 $a_i$，每个连续段可以和其他连续段建立至多 $a_i$ 个匹配，任意匹配之间不交，或者不存在匹配 $(a, b), (c, d)$ 满足 $a < c < b < d$，最小化未建立的匹配数．可以通过调整法证明，当不存在一个 $a_i$ 大于 $\frac{1}{2} \sum a_i$ 的时候，最小的未建立匹配数总是 $0$．故答案为 $\max\{\frac{1}{2} \sum a_i, \max a_i\}$

Codeforces 2217E Definitely Larger

考察序列 $d$，对于 $d_i = 0$ 的位置，它不能被任何位置支配，所以这些位置必须填入当前能填的最大值．故我们考虑从大到小，将 $n \sim 1$ 填入到序列 $q$．若有多个 $d_i = 0$ 的位置，每次选取 $i$ 最小的位置填，显然是合法的．填入一个值之后，后续填入的值必定比这个值小，所以我们产生了多对偏序关系．减小对应的 $d_i$ 后，会产生新的 $d_i = 0$ 的位置，迭代填入即可．

显然此算法可以构造出一组合法解，如何证明对于存在解的输入，这个算法总是能构造出一组解？我不知道．

Codeforces 2217F Interval Game

考察在怎样的局面下 Alice 存在必胜策略．对于选取的区间 $[l_1, r_1], [l_2, r_2]$，游戏可看作有 $4$ 堆石子，石子个数分别为 $l_1 - 1, x_1 - r_1, l_2 - 1, x_2 - r_2$ 的 nim 游戏．当这 $4$ 个数异或和不为 $0$ 时，Alice 必胜．

考察 Alice 选取第一个区间的操作，她能够取到怎样的异或和？我们可以取 $l_1 = 1$，这样可以构造出 $0 \sim x_1 - 1$ 中所有的数．记录 $a = l_1 - 1, b = x_1 - r_1$，由于 $a + b = 2(a \operatorname{and} b) + a \operatorname{xor} b, a \operatorname{and} b \ge 0$，且 $a + b \le x_1 - 1$，所以 $a \operatorname{xor} b \le x_1 - 1$．故 Alice 能且只能构造出 $0 \sim x_1 - 1$．

要让 Alice 获胜的概率最大，我们可以枚举 Alice 构造出的异或和，尝试找到一个值 $x$，使得在所有可能的 $l_2, r_2$ 取值中，满足 $(l_2 - 1) \operatorname{xor} (x_2 - r_2) = x$ 的情况最少．为此，我们尝试对于每个 $0 \le x < x_1$，计算有多少对 $l_2, r_2$ 满足 $(l_2 - 1) \operatorname{xor} (x_2 - r_2) = x$，记作 $c_x$．

不妨枚举 $l_2 - 1$，考虑计算 $r_2$ 取遍 $0 \sim x_2 - l_2$ 时对序列 $c$ 的影响．可以注意到，对于 $a \operatorname{xor} b$，当 $b$ 取遍 $k \times 2^t \sim k \times 2^t + 2^t - 1$ 时，$a \operatorname{xor} b$ 的取值也是一个区间．考虑如何利用这一点，我们可以枚举 $x_2 - l_2$ 要保留的前缀长度，然后钦定退掉后缀的第一位，使得后缀的剩余位可以取遍所有状态，这样就将可能的异或值贡献拆分成了若干个区间加，差分处理即可．

或者有一个更形象的理解，考察一个插入了所有 i32 的 trie 树，我们考察从根节点走到 $l_2 - 1$ 对应叶子的过程，每次在某个节点走 1 边的时候，通过 0 边可达的子树可以的状态可以取遍，依旧差分处理区间加即可．