AT_arc199_a [ARC199A] Flip Row or Col 2

我无法言说我对这道题的赞美。

首先考虑 \(< \frac{n}{4}\) 这个限制比较诡异，我们估计整个题的做法都是依赖这个限制的。

有了 \(\frac{n}{4}\)，很难让人不从 \(\frac{n}{2}\) 下手，以下是这个题的做法：

• 先将第一行操作成 \(0\)。
• 对于接下来每一行，如果 \(1\) 的个数 \(< \frac{n}{2}\) 则不反转，否则翻转，这是因为如果要更改必然要使得第一行的 \(1\) 的个数 \(\ge \frac{n}{4}\)。
• 对于列的操作顺序就很清晰了，如果这一行是 \(c_i\)，那么不反转，如果是 \(n - c_i\)，就反转。

很容易领会这个做法的正确性，但是怎么想到的我只能说灵机一动。