Reflection

题目描述

农夫约翰有一块正方形画布，用一个 $N$ 行 $N$ 列的网格表示（$2 \leq N \leq 2000$，且 $N$ 为偶数）。他按如下步骤给画布上色： 首先，他用穿过画布中心的水平线和竖直线，将画布分成四个大小相同的象限。 接着，他在画布的右上象限画出一幅漂亮的画。右上象限中的每个格子要么被涂色（用字符 '#' 表示），要么未被涂色（用字符 '.' 表示）。 最后，由于他对这幅画非常自豪，他将其沿前面提到的水平线和竖直线进行反射，复制到画布的其他象限中。 例如，设 $N=8$，并且 FJ 在步骤 2 中在右上象限画了如下图案： .#.. .#.. .##. .... 那么在步骤 3 中沿水平线和竖直线反射到其他象限后，整个画布会变成： ..#..#.. ..#..#.. .##..##. ........ ........ .##..##. ..#..#.. ..#..#.. 然而，当 FJ 睡觉时，贝茜闯入他的谷仓并偷走了他珍贵的画布。她彻底破坏了画布——擦掉了一些已涂色的格子，又额外涂上了一些格子！在 FJ 醒来之前，她又把画布还给了他。 FJ 希望修改画布，使其再次满足反射条件：也就是说，它应当是由右上象限反射到其余三个象限得到的结果。由于资源有限，他希望用尽可能少的操作来完成，其中一次操作指的是给一个格子涂色，或从一个格子去除涂色。 给定贝茜破坏后的画布，以及对画布的一系列 $U$（$0\le U \leq 10^5$）次更新，每次更新都会将某一个格子的字符翻转：如果它是 '#' 则变为 '.'，反之亦然。在任何更新之前，以及每次更新之后，输出 FJ 为使反射条件成立所需的最少操作次数 $x$。

输入格式

第一行包含整数 $N$ 和 $U$。 接下来 $N$ 行每行包含 $N$ 个字符，表示贝茜破坏后的画布。每个字符为 '#' 或 '.'。 接下来 $U$ 行每行包含整数 $r$ 和 $c$，其中 $1 \leq r, c \leq N$，表示对画布中从上往下第 $r$ 行、从左往右第 $c$ 列的格子进行一次更新。

输出格式

输出 $U+1$ 行，分别表示任何更新之前以及每次更新之后的 $x$。

4 5
..#.
##.#
####
..##
1 3
2 3
4 3
4 4
4 4

4
3
2
1
0
1

提示

下面这个画布满足反射条件，并且与原始画布相比需要 4 次操作： ....

.... 无法用少于 4 次操作让原始画布满足反射条件。 在更新 $(1, 3)$ 之后，画布变为： .... ##.#

..## 此时需要 3 次操作才能让画布满足反射条件。 在更新 $(2, 3)$ 之后，画布变为： ....

..## 此时需要 2 次操作才能让画布满足反射条件。 计分： 测试点 2-3：$N \le 4$ 测试点 4-6：$U \le 10$ 测试点 7-16：无额外限制。 题目来源：Chongtian Ma

标签: USACO|2025|Bronze

来源

USACO|2025|Bronze