[ARC133C] Row Column Sums 题解

题目链接：[AGC004D] Teleporter

题意：

我们有一个 $H$ 行 $W$ 列的网格。

Snuke 要在每个格子里写一个介于 $0$ 和 $K-1$ 之间的整数。必须满足以下条件：

对于每个 $1 \le i \le H$，第 $i$ 行的整数之和对 $K$ 取模的结果为 $A_i$。

对于每个 $1 \le i \le W$，第 $i$ 列的整数之和对 $K$ 取模的结果为 $B_i$。

确定是否可能在方格中写入整数以满足条件。如果可能，还需找到所写整数的最大可能和。

输入格式：

$H~W~K$

$A_{1}~A_{2}~\cdots~A_{H}$

$B_{1}~B_{2}~\cdots~B_{W}$

输出格式：

如果不可能在方格中写入整数以满足条件，则输出 -1。如果可能，输出所写整数的最大可能和。

数据范围：

$1 \le H, W \le 2\times10^5,~2 \le K \le 2\times 10^5,~0 \le A_i \le K-1,~0 \le B_i \le K-1$

首先无解的情况很显然，即 $\sum A_i \not\equiv \sum B_i \pmod{K}$ 。接下来我们考虑有解的情况。

这种题没有要求构造方案，只要求最后的和，不难发现其实就是一道结论题。

考虑把所有格子都填上 $k-1$ ，并分别记 $C_i,D_i$ 为行、列需要减少的数值。

设 $Z=\max\left\{\sum C_i,~\sum D_i\right\}$ ，则我们至少需要减少 $Z$ ，此时的总和为 $HW\times(K-1) - Z$ 。

可以证明，存在一种构造方法使得我们只需要减去 $Z$ ，下面我们来证明这个结论。

因为 $\sum C_i\equiv\sum D_i\pmod K$ ，所以我们可以对 $C_1$ 或 $D_1$ 加入 $k$ 的倍数，使得 $\sum C_i = \sum D_i = Z$ 。

现在，重复以下步骤 $Z$ 次：

找到所有满足 $C_i \ge 1 \land D_j \ge 1$ 的 $(i,j)$ ，使 $(i,j)$ 填的数减 $1$ ，这会使得 $C_i,D_j$ 同时减 $1$ 。

这里 $(i,j)$ 的值至多被减去 $\min(C_i,D_i) \le K-1$ 次，因此不会出现负数。$\square$

时间复杂度 $\mathcal{O}(W + H)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))

int h,w,k,a[N],b[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> h >> w >> k;
    for(int i = 1; i <= h; i++) {
        cin >> a[i]; a[i] = ((k - 1) * w - a[i]) % k; a[i] += a[i - 1];
    }
    for(int i = 1; i <= w; i++) {
        cin >> b[i]; b[i] = ((k - 1) * h - b[i]) % k; b[i] += b[i - 1];
    }
    int x = a[h], y = b[w];
    if(x % k != y % k) cout << -1 << '\n';
    else cout << (h * w * (k - 1) - max(x,y));
    return 0;
}

---

参考文献：

[1] https://atcoder.jp/contests/arc133/editorial/3292