题解：P15661 [ICPC 2025 Jakarta R] Grid Game 2×2

· · 题解

题目大意：二维平面游戏，初始有 n 个黑格子，每次可以选择一个坐标 (x,y) 的黑格子，翻转任意多个以它为右上角的边长 2^k 的正方形区域，最后把 (x,y) 强制变成白格子。先把所有格子变白的获胜。

首先这显然是一个Nim游戏，往异或方向思考。手玩了几个样例有点迷，于是先思考简单版本：假设所有点的 x=y。 此时每次操作后新增的 x \neq y 的黑格子都是对称的，可以镜像策略消灭，于是问题转化为一个一维版本：有 n 个位置 x_i 是黑色的，每次可以选择某个 x_i, 并翻转任意多个区间 [x_i-2^k+1,x_i-1] 内的格子，以及 x_i 本身（需要满足 2^k \leq x_i）。

我们思考一个区间的翻转会改变什么？以下部分 lowbit 指的都是位数。我们令 u=lowbit(x_i), 当选择的 k <= u 时，区间内 lowbit < k-1 的数字都是偶数个，而 lowbit=k-1 的数字是奇数个。从而我们可以选择恰当的 k 的集合去任意修改整个数组 lowbit 值的异或值。当 k>u 时修改结果比较混乱，但最高位一定会被修改，没法保持不变。所以如果当前所有数字 lowbit 的异或结果为0，则操作后一定变成不为0（因为 x_i 必须被修改），故先手方的获胜条件是所有 lowbit 异或结果不为0.

一维问题解决后，我们推广到二维。观察一会儿后发现选择 f(x,y)=min(lowbit(x),lowbit(y)) 即可，即当才做选择的 k \leq f(x,y) 时，都能让所有数字的 f(x_i,y_i) 第 k-1 位异或和改变。所以结论是：先手方获胜条件为所有位置的 min(lowbit(x),lowbit(y))=lowbit(x|y) 异或结果不为0。时间复杂度 O(n).

证明可以用归纳法证明游戏的SG函数,读者自证不难。