「解题报告」ARC135D Add to Square

这种题的第一想法应当是找不变量。

如果给原图黑白染色，那么每次操作都是操作两个黑格两个白格，那么黑格与白格的差不变。如果我们给黑格的数乘上 \(-1\)，那么就是所有格子的和不变。

同时由于是 \(2 \times 2\)，还能发现一行 / 一列的和不变。于是猜测当每一行的和与每一列的和都与原来相等时，该结果合法。

考虑将原来的与结果的 \([1, h - 1] [1, w - 1]\) 的所有格子全部消为 \(0\)，这样每一行相等、每一列相等说明这几个数相等，说明可以从原局面得出。

那么相当于我们有 \(\{x_1, x_2, \cdots, x_h\}\) 与 \(\{y_1, y_2, \cdots, y_w\}\)，每次选择一个 \((i, j, d)\)，使 \(x_i \gets x_i - d, y_j \gets y_j - d, b_{i, j} \gets b_{i, j} + d\)，答案加 \(|d|\)，最终要求让所有的 \(x, y\) 都变成 \(0\)，使答案最小。

首先答案的一个下界为 \(\max \{\sum |x_i|, \sum |y_i|\}\)。我们可以构造出这个下界。

首先一直选两个都大于 \(0\) 或都小于 \(0\) 的 \(x\) 和 \(y\)，将它们其中一个变为 \(0\)。由于 \(\sum x_i = \sum y_i\)，说明现在肯定 \(x\) 或者 \(y\) 全部为 \(0\)，接下来我们每次把不为 \(0\) 的一遍的一个大于 \(0\) 的和一个小于 \(0\) 的，其中一个变为 \(0\)，这样一定可以使答案最终都变为 \(0\)，而总花费也取到了下界。那么根据这个过程构造答案就行了。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
int h, w;
long long a[MAXN][MAXN], x[MAXN], y[MAXN];
long long b[MAXN][MAXN];
int main() {
    scanf("%d%d", &h, &w);
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            scanf("%lld", &a[i][j]);
            a[i][j] *= ((i + j) & 1) ? -1 : 1;
            x[i] += a[i][j];
            y[j] += a[i][j];
        }
    }
    long long ans = 0;
    while (true) {
        bool flag = false;
        for (int i = 1; i <= h; i++) if (x[i] > 0) {
            for (int j = 1; j <= w; j++) if (y[j] > 0) {
                long long delta = min(x[i], y[j]);
                x[i] -= delta, y[j] -= delta, ans += delta;
                b[i][j] += delta;
                flag = true;
            }
        }
        for (int i = 1; i <= h; i++) if (x[i] < 0) {
            for (int j = 1; j <= w; j++) if (y[j] < 0) {
                long long delta = min(-x[i], -y[j]);
                x[i] += delta, y[j] += delta, ans += delta;
                b[i][j] -= delta;
                flag = true;
            }
        }
        if (!flag) break;
    }
    while (true) {
        bool flag = false;
        for (int i = 1; i <= h; i++) if (x[i] > 0) {
            for (int j = 1; j <= h; j++) if (x[j] < 0) {
                long long delta = min(x[i], -x[j]);
                x[i] -= delta, x[j] += delta, ans += 2 * delta;
                b[i][1] += delta;
                b[j][1] -= delta;
                flag = true;
            }
        }
        for (int i = 1; i <= w; i++) if (y[i] > 0) {
            for (int j = 1; j <= w; j++) if (y[j] < 0) {
                long long delta = min(y[i], -y[j]);
                y[i] -= delta, y[j] += delta, ans += 2 * delta;
                b[1][i] += delta;
                b[1][j] -= delta;
                flag = true;
            }
        }
        if (!flag) break;
    }
    printf("%lld\n", ans);
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            printf("%lld ", b[i][j] * (((i + j) & 1) ? -1 : 1));
        }
        printf("\n");
    }
    return 0;
}