[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