正负消除问题

题意：

有一个 \((2n+1)\) 大小的正方形，每个位置放着 + 或 -，每次可以选取一个排列 \(p_i\)，将 \((i, p_i)\) 改变状态。

证明：一定可以使得最后 - 不超过 \(2n\) 个。

思路：

这个操作比较复杂，我们先考虑简化。

不难想到用两次操作一起来抵消某些操作，经过观察，我们发现两次操作可以使得的一个矩形的四个角颜色反转。

借助这个观察，我们可以通过消除除了最后一行最后一列之外的 - 使得只有最后一行最后一列有 -，其它都是 +。

这样就小于等于 \(4n+1\)。

继续简化。

我们考虑主对角线，不难发现，如果最后一行的某个 - 列编号和最后一列某个 - 行编号相同，我们可以通过底角和主对角线构造矩形，消去这两个 -。

这样我们把原图剖分成 \(2n\) 个 r 字形和一个底角，每个 r 字形都最多一个 -，答案已经小于等于 \(2n+1\) 了。

考虑如何消去底角的 -。

如果最后一行最后一列同时有，可以组成一个矩形使得三个角都是 -，可以减少到 \(2n-1\)。

否则，我们不妨设只有最后一列和主对角线有，显然每一行恰好一个。

我们运用一次最根本的操作，消去主对角线，这时候就是若干行有 2 个，若干行没有。

这时候只用选取两行便能完成一次消除。

考虑到最差情况消去主对角线后还剩 \(2n+2\) 个，消去以此减少 2 个，刚好是 \(2n\) 个。

很有意思的一道题。