NOIP 提高组初赛 · NOIP 2017 提高组初赛试题 第 21 题

如右图所示，共有 $13$ 个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变（由 $1$ 变 $0$，或由 $0$ 变 $1$）。现在要使得所有的格子中的数字都变为 $0$，至少需要_________次操作。 

这题本质是异或线性方程组，但考场时间不够列方程。核心心法是：先定好第一行要不要操作，然后从上往下顺推——因为第 i 行第 j 列的 1 只能靠第 i 行或第 i-1 行的操作消除，一旦第 i-1 行操作定死，第 i 行第 j 列的 1 就全靠第 i 行第 j 列自己来消，所以第 i 行每个格子要不要操作完全由第 i-1 行决定。最后检查最后一行是否全消。这样就能在 O(n) 内找到唯一解，再数操作次数。

最容易犯两个错：一是以为可以随便选几个格子操作就完事，其实操作顺序不影响最终结果，但必须保证每步消的是当前行留下的 1，否则最后会留残；二是忽略最后一行，往往只看到前几行消完了就以为结束了，结果最后一行还剩下几个 1，导致操作次数算少。另外，有人会试图用贪心从左上角开始逐个消，但那样会打乱后面行的依赖关系，导致无法全局最优。

考点概念：格点翻转（十字操作）

每个操作翻转以该格为中心的十字（5 个格子）。目标：全部变 0。

命题视角

命题人想考的是「异或线性方程组」，但数据规模很小（13 格），直接列方程解太繁琐，所以设计了这种「从上到下顺推」的套路。他们喜欢在最后一行挖坑——很多学生只看到前几行消完就以为结束了，结果最后一行还剩下几个 1，导致操作次数算少。另外，有人会以为可以随便选几个格子操作就完事，其实操作顺序不影响最终结果，但必须保证每步消的是当前行留下的 1，否则最后会留残。