B4229 [常州市程序设计小能手 2024] 棋盘 题解

· · 题解

小能手比赛居然在洛谷上有了（喜）。

首先，那些黑白相间的格子就相当于一个白色的格子通过操作弄出来的，所以先倒推回去，这就相当于在偶数行和偶数列进行操作。

然后，我们把每一行和每一列操作的次数记录下来，如果操作奇数次，记为 1（因为操作 1 次和操作奇数次数一样的），偶数次就记为 0。

如样例：

接下来就要想想怎么计算联通块了，

比如我们写出某一个矩阵行和列的操作数：

相邻两行的操作数如果奇偶性相同，那么他们每一列都是一样的，就构成了联通块，否则，他们每一列都是不一样的，就会被划分到两个不同的连通块，所以答案就是行操作次数奇偶性相同的连通块个数，乘上列连通块个数（如果不太能理解的话可以看一下下图）

列也是同理：

最后我们再填上颜色：

做到这里的时候结论就已经很显然了。

并且这个显然可以在修改的过程中 O(1) 求出（修改某一个行或者某一个列只要关心相邻的行或者列就可以维护答案），然后一开始的答案暴力求出就可以了。

总共的时间复杂度 O(q)。

最后可以再对照样例看一下：