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

首先，这题的 $0 \le a_{i, j} \le 10^6$ 这个限制比较恶心，所以先不考虑这个限制，只需要找到一组合法的 $a$ 即可。这样问题就很简单了：钦定 $a$ 的最下面一行和最右边一列是 $0$，然后按照 $b$ 的限制从右下到左上一个个推即可。这部分时间复杂度可以做到 $\mathcal O(nm)$。 下面考虑调整这个 $a$ 矩阵的值，使得其对应的 $b$ 矩阵不变，但是每个 $a_{i, j}$ 的大小都在 $[0, 10^6]$ 之间。我们发现，对于一个 $x$，如果对一行的所有数字依次进行 $+x,-x,+x,-x,\dots$ 的操作，那么对应的 $b$ 矩阵不会发生变化，对于一列同理。下面就设 $r_i$ 为在第 $i$ 行上操作的 $x$ 值，设 $c_i$ 为在第 $i$ 列上操作的 $x$ 值。 现在，对于每个格子 $(i, j)$ 的值的限制，我们就可以将其转化为 $r_i$ 与 $c_i$ 的和或者差的限制。设 $A_{i, j}$ 表示 $(i, j)$ 格子增加的值，则 $A$ 矩阵如下： $$ \left( \begin{matrix} r_1+c_1 & -r_1+c_2 & r_1+c_3 & \cdots\\ r_2-c_1 & -r_2-c_2 & r_2-c_3 & \cdots\\ r_3+c_1 & -r_3+c_2 & r_3+c_3 & \cdots\\ \vdots & \vdots & \vdots & \ddots \end{matrix} \right) $$ 对于一个位置 $a_{i, j}$，$A_{i, j}$ 必须满足 $-a_{i, j} \le A_{i, j} \le 10^6 - a_{i, j}$。 但是目前矩阵中值的形式很不统一，既有 $x+y$ 的形式也有 $x-y$ 的形式。考虑对于所有偶数的 $i$，将 $r_i$ 取相反数，对于所有奇数的 $j$，将 $c_j$ 取相反数，则 $A$ 矩阵就变成： $$ \left( \begin{matrix} r_1-c_1 & c_2-r_1 & r_1-c_3 & \cdots\\ c_1-r_2 & r_2-c_2 & c_3-r_2 & \cdots\\ r_3-c_1 & c_2-r_3 & r_3-c_3 & \cdots\\ \vdots & \vdots & \vdots & \ddots \end{matrix} \right) $$ 这样矩阵中所有的值都变成 $x-y$ 的形式了，于是 $-a_{i, j} \le A_{i, j} \le 10^6 - a_{i, j}$ 就可以转化为 $-a_{i, j} \le x-y \le 10^6 - a_{i, j}$ 的形式，就变成了一个差分约束问题。 这个差分约束模型中共有 $n+m$ 个变量，有 $2nm$ 个约束，进行 SPFA 最短路的时间复杂度为 $\mathcal O(nm(n+m))$。但是，众所周知，SPFA 的复杂度永远是卡不满的（即使图中存在负环，即无解的情况，也只是部分点被松弛 $n + m$ 次），所以可以通过。 附上考场上写的代码： ``` cpp #include <bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() #define SZ(x) ((int)(x).size()) #define loop(i, a) for (int i = 0; i < (a); ++i) #define cont(i, a) for (int i = 1; i <= (a); ++i) #define circ(i, a, b) for (int i = (a); i <= (b); ++i) #define range(i, a, b, c) for (int i = (a); (c) > 0 ? (i <= (b)) : (i >= (b)); i += (c)) #define pub push_back #define pob pop_back #define mak make_pair #define mkt make_tuple typedef long long ll; typedef long double lf; const int Inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3fll; int T; int n, m; int a[305][305], b[305][305]; vector<pair<int, int> > egs[605]; bool inq[605]; int tms[605]; ll dis[605]; void solve() { scanf("%d%d", &n, &m); cont(i, n - 1) cont(j, m - 1) scanf("%d", a[i] + j); memset(b, 0, sizeof(b)); range(i, n, 1, -1) range(j, m, 1, -1) b[i][j] = a[i][j] - b[i + 1][j] - b[i + 1][j + 1] - b[i][j + 1]; cont(i, n + m) egs[i].clear(); cont(i, n) cont(j, m) { int mx = 1000000 - b[i][j], mn = -b[i][j]; if (!((i + j) & 1)) egs[j + n].pub(mak(i, mx)), egs[i].pub(mak(j + n, -mn)); else egs[j + n].pub(mak(i, -mn)), egs[i].pub(mak(j + n, mx)); } deque<int> q; memset(inq, 0, sizeof(inq)); memset(tms, 0, sizeof(tms)); memset(dis, Inf, sizeof(dis)); dis[1] = 0; q.pub(1); while (SZ(q)) { int now = q.front(); q.pop_front(); ++tms[now]; inq[now] = 0; if (tms[now] > n + m) { puts("NO"); return; } loop(i, SZ(egs[now])) { int to = egs[now][i].first, siz = egs[now][i].second; if (dis[to] > dis[now] + siz) { dis[to] = dis[now] + siz; if (!inq[to]) { if (SZ(q) && dis[to] < dis[q[0]]) q.push_front(to); else q.pub(to); inq[to] = 1; } } } } cont(i, n) cont(j, m) { if ((i + j) & 1) b[i][j] -= dis[i]; else b[i][j] += dis[i]; if ((i + j) & 1) b[i][j] += dis[j + n]; else b[i][j] -= dis[j + n]; } puts("YES"); cont(i, n) cont(j, m) printf("%d%c", b[i][j], " \n"[j == m]); } int main() { freopen("matrix.in", "r", stdin); freopen("matrix.out", "w", stdout); scanf("%d", &T); while (T--) solve(); return 0; } ```