题解：CF226D The table

Eason_cyx · 2026-07-23 19:54:49 · 题解

考虑如下一个想法：

枚举所有行和所有列，如果其值为负的，就翻转。

这显然是错的，因为你翻完行再翻列的时候可能又把行变成负的了。

那么一个自然的修补方法就是我们多做几次。

实际上，至多做 10^6 次即可通过。下面我们来证明这个结论：

因为如果一行或一列的和是负的，那么其翻转之后，整个数组的总和至少增加 2（最少就是 -1 \to 1）；但因为 |a_i| \le 100，所以整个数组的和 s 必须满足 -10^6 \le s \le 10^6，也就是说，我们最多只会进行 10^6 次操作。因此这样做是对的。

时间复杂度 O(nmV(n+m))。

注意记录每行每列翻了几次即可，如果翻了偶数次相当于没翻。