2026 年北京预赛

提示

先独立尝试，再展开工具说明与想法来源。

思路

可不用拉普拉斯矩阵：次数最大的点满足 $d (v) q_{v} = \sum w (uv) q_{u}$ ，正权平均等于最大值，故邻点全取同一最大值，沿连通图传播。补配置必须非负；周期中某点硬币若超过发送总量就永远不能再次操作，这正好保证非负。

想法从哪来：固定染色后，每次操作其实只是沿相邻边发送规定数量，先把颜色换成边权。试数总硬币，只知它守恒还不够；固定总量下配置有限，无限操作必有重复，于是应转而研究一个周期。周期中若某点操作次数最多，平衡式迫使所有邻点次数同样多，连通性便把相等传播到全图。再试把每点硬币数改成“该点发送总量减现有量”，这会把一步合法操作反向。原周期和补周期的下界夹住总量，才得到固定染色的精确总数。最后把权重和拆成边数与异色边数，构造从整列同色开始，再翻动首行的一段调节余数。

把棋盘格看成图的顶点，并把同色边、异色边分别赋权 $1, 2$ 。一次操作就是在某顶点恰有其加权度数枚硬币时，将相应边权的硬币发往各邻点。先用周期与补配置证明：固定染色时总数被迫等于全图边权和；再转化为网格图二色割边数的取值问题。

解答

把 $n^{2}$ 个格看成网格图 $G$ 的顶点。相邻同色格之间的边权记为 $1$ ，异色格之间的边权记为 $2$ 。设

d (v) = u \sim v \sum w (uv), W = e \in E (G) \sum w (e) .

按操作规则，顶点 $v$ 可被操作时恰有 $d (v)$ 枚硬币；操作后它变为 $0$ ，并沿每条邻边发送 $w (uv)$ 枚硬币。

先证明固定染色时，能无限操作的硬币总数必为 $W$ 。总数不变，因而固定总数下只有有限多个配置。无限操作序列中必有某个配置重复，两次出现之间构成非空合法周期。设周期中各顶点的操作次数为 $q_{v}$ 。周期前后配置相同，所以

d (v) q_{v} = u \sim v \sum w (uv) q_{u} .

即加权图拉普拉斯矩阵作用在 $(q_{v})$ 上为零。网格图连通且边权为正，故所有 $q_{v}$ 相等；周期非空，所以每个顶点都在周期中被操作。

周期中的任一配置均满足 $0 \leq c (v) \leq d (v)$ 。否则若 $c (v) > d (v)$ ，以后别的操作只会使 $c (v)$ 增加，而 $v$ 再也不能恰有 $d (v)$ 枚硬币，因而不可能回到原配置。把周期向过去循环延拓，并在当前时刻记每个顶点最近一次操作的时刻。对每条边，把它从最近操作较晚的端点指向较早的端点。较晚端点在较早端点最后清空之后，至少沿此边发送过一次硬币，所以当前较早端点至少保留了该边权的贡献。逐点求和即得

v \sum c (v) \geq W . (3)

再定义补配置 $\overset{c}{ˉ} (v) = d (v) - c (v)$ 。若原周期的一步从 $c$ 操作 $v$ 得到 $c^{'}$ ，则从 $\overset{c}{ˉ}^{'}$ 操作同一个 $v$ 恰好得到 $\overset{c}{ˉ}$ 。因此把周期倒序便得到补配置的合法周期。补配置的总数为

v \sum d (v) - v \sum c (v) = 2 W - v \sum c (v) .

对补周期应用 (3)，得 $2 W - \sum_{v} c (v) \geq W$ 。结合 (3)，可知

v \sum c (v) = W . (4)

反之，固定染色后总数 $W$ 一定可以实现无限操作。任取顶点全序 $v_{1}, v_{2}, \dots, v_{n^{2}}$ ，初始时在 $v_{i}$ 放置所有连接到较晚顶点 $v_{j}$ 的边权之和。于是 $v_{1}$ 可先操作；当前面的顶点依次操作完后， $v_{i}$ 已从所有较早邻点收到相应边权，加上原先朝向较晚邻点的硬币，恰为 $d (v_{i})$ ，所以可继续操作。依次操作完所有顶点后，每个顶点又回到初始配置，故该序列可以无限循环。

网格图共有

E = 2 n (n - 1)

条边。若异色邻边数为 $b$ ，则

W = (E - b) + 2 b = E + b . (5)

因此只需求二色染色的割边数 $b$ 的所有可能值。

当 $n = 2$ 时，网格图是一个四边形，割边数只能为 $0, 2, 4$ ，由 (5) 得硬币总数为

4, 6, 8 .

以下设 $n \geq 3$ 。网格图每条边都在某个四边形回路上，所以没有桥，割边数不可能为 $1$ 。把任意染色与棋盘的黑白相间染色逐格异或，会把每条边的“同色/异色”状态互换，故若 $b$ 可取，则 $E - b$ 也可取；于是 $E - 1$ 也不可能取到。

下面构造其余各值。先令每一列内部同色，并使相邻列的颜色在恰好 $q$ 个列间边界处改变，则割边数为 $q n$ 。再把第一行最左边的 $k$ 个格全部反色，其中 $1 \leq k \leq n - 1$ 。这样 $k$ 条竖边由同色变为异色；第一行只有第 $k$ 、 $k + 1$ 列之间的一条横边改变状态。若该列间边界原来变色，割边数净增 $k - 1$ ；若原来不变色，割边数净增 $k + 1$ 。

当 $q = 0$ 时，由不翻色或令 $k = 1, 2, \dots, n - 1$ ，可得到 $0, 2, 3, \dots, n$ 。当 $1 \leq q \leq n - 2$ 时，可按需要指定第 $k$ 个列间边界为变色或不变色，并在其余边界中安排剩下的 $q$ 次变色。取变色边界 $k = r + 1$ 可得到净增 $r = 0, 1, \dots, n - 2$ ；取不变色边界 $k = r - 1$ 可得到净增 $r = 2, 3, \dots, n$ 。故从 $q n$ 到 $(q + 1) n$ 的每个整数都能取到。综上， $0$ 到 $n (n - 1) = E /2$ 之间除 $1$ 外均能取到；再用异或变换， $E /2$ 到 $E$ 之间除 $E - 1$ 外也均能取到。因此

b \in {0, 2, 3, \dots, E - 2, E} .

代入 (5)，当 $n \geq 3$ 时硬币总数的所有可能值为

E, E + 2, E + 3, \dots, 2 E - 2, 2 E, E = 2 n (n - 1) .

复核

周期中各顶点操作次数相等来自连通正权图拉普拉斯矩阵的核；补配置在倒序中每一步均恰好合法。构造部分覆盖了下半区间的每个数，并通过棋盘交错染色异或准确映到 $b \mapsto E - b$ ，两个被排除的值分别对应网格图及其异或图中的单边割。

方法总结

这类“清空并按边发送”的过程先转成加权图。有限状态给出周期，最近操作时刻定向给出总量下界，而 $d - c$ 的补配置把过程反向，从而逼出唯一总量。剩下的颜色影响只体现在割边权上，可用规则染色与局部翻色连续构造其取值谱。

作答

解析

提示

思路

解答

复核

方法总结