B - Plus Matrix

题意

$N$ 行 $N$ 列の非負整数を成分とする行列 $C$ が与えられます。すべての $(i,j)$ について $C_{i,j}=A_i+B_j$ を満たすような非負整数列 $A_1,A_2,\ldots,A_N$ と $B_1,B_2,\ldots,B_N$ の組が存在するか判定し、存在するなら一つ出力してください。

解析

首先，$A$ 的差分和 $C$ 每一行的差分必须相等。根据这一点，加上 $A$ 只包含非负整数的限制，可以构造出一个最小的 $A$ (更小的 $A$ 更容易让 $B$ 满足非负的限制)。之后根据定义求出 $B$ 即可。

实现

#include <bits/stdc++.h>

const int maxn = 5e2 + 19;

int n, c[maxn][maxn], a[maxn], b[maxn];

int main(){
    std::scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            std::scanf("%d", c[i] + j);
    for(int i = 1; i <= n; ++i)
        a[i] = c[i][1];
    int min = a[1];
    for(int i = 2; i <= n; ++i)
        min = std::min(min, a[i]);
    for(int i = 1; i <= n; ++i)
        a[i] -= min;
    for(int i = 1; i <= n; ++i){
        b[i] = c[1][i] - a[1];
        if(b[i] < 0){
            std::puts("No");
            return 0;
        }
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(c[i][j] != a[i] + b[j]){
                std::puts("No");
                return 0;
            }
    std::puts("Yes");
    for(int i = 1; i <= n; ++i)
        std::printf("%d ", a[i]);
    std::puts("");
    for(int i = 1; i <= n; ++i)
        std::printf("%d ", b[i]);
    std::puts("");
}

来源

AtCoder Regular Contest 115 B - Plus Matrix

评论