[省选联考 2021 A 卷] 矩阵游戏

比较有意思的一道题。

首先不考虑 \(a_{i, j}\) 的限制随便求，然后开始调整。你发现对于每行，奇数列 \(+x\) 偶数列 \(-x\) 不会变，列也同理，假设第 \(i\) 行的 \(x\) 为 \(r_i\), 第 \(j\) 列的 \(x\) 为 \(c_j\)。然后考虑对 \(a\) 加上一个矩阵 \(A\)，\(A_{i, j} = (-1)^{2\mid i+1}r_i - (-1)^{2\mid j+1}c_j\)。然后你发现这样会有加和，不能跑差分约束，调整一下，\(\forall 2 \mid i, r_i \leftarrow -r_i, \forall 2 \nmid j, c_j \leftarrow -c_j\)，就都是差的形式了。然后差分约束即可，时间复杂度 \(\mathcal{O}(nm(n+m))\)。

点击查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 i128;
typedef pair<int, int> pii;
const int N = 3e2 + 10, V = 1e6, mod = 998244353;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {cout << arg << ' ';dbg(args...);
}
namespace Loop1st {
int n, m, b[N][N], a[N][N];
ll dis[N << 1];
vector<pii>e[N << 1];
void main() {memset(dis, 0x3f, sizeof dis); memset(a, 0, sizeof a);cin >> n >> m;for (int i = 0; i <= n + m; i++) e[i].clear();for (int i = 1; i <= n + m; i++) e[0].push_back({i, 0});for (int i = 1; i < n; i++) for (int j = 1; j < m; j++) cin >> b[i][j];for (int i = n - 1; i; i--) {for (int j = m - 1; j; j--) {a[i][j] = b[i][j] - a[i + 1][j] - a[i][j + 1] - a[i + 1][j + 1];}}for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {if ((i + j) & 1) e[n + j].push_back({i, a[i][j]}), e[i].push_back({n + j, V - a[i][j]});else e[i].push_back({n + j, a[i][j]}), e[n + j].push_back({i, V - a[i][j]});}dis[0] = 0;int t = 1;for (t = 1; t <= n + m + 2; t++) {bool ok = 0;for (int u = 0; u <= n + m; u++) {for (auto [v, w] : e[u]) if (dis[v] > dis[u] + w) {dis[v] = dis[u] + w;ok = 1;}}if (!ok) break;}if (t > n + m + 2) {cout << "NO\n";return ;}cout << "YES\n";for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {// dbg("###", i, j, dis[i], dis[n + j], a[i][j]);if ((i + j) & 1) cout << a[i][j] + dis[n + j] - dis[i] << " \n"[j == m];else cout << a[i][j] + dis[i] - dis[n + j] << " \n"[j == m];}}
}}
int main() {// freopen("data.in", "r", stdin);// freopen("data.out", "w", stdout);ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int T = 1;cin >> T;while (T--) Loop1st::main();return 0;
}