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

· · 题解

题目传送门

题目大意

有一个 n \times m 的矩阵 A，你用其生成了一个 (n-1) \times (m-1) 的矩阵 B，满足 b_{i, j}=a_{i,j}+a_{i,j+1}+a_{i+1,j}+a_{i+1,j+1}

现给出矩阵 B，要求得到原来的矩阵 A，元素值域 [0,\ 10^6]

丢掉限制，那么这道就是个弱智题。

因为

b_{i, j}=a_{i, j}+a_{i,j+1}+a_{i+1,j}+a_{i+1,j+1} a_{i, j}=b_{i, j}-a_{i,j+1}-a_{i+1,j}-a_{i+1,j+1}

所以我们选择从矩阵右下角逆推，这样在求 a_{i, j} 的时候，剩下四个元素就全部是已知的了。

但是我们还得考虑值域的影响。

思考什么样的操作不会影响到 B 矩阵。

由于 B 矩阵的生成相当于一个 4 \times 4 的矩阵：

a_{i, j} & a_{i, j+1}\\ a_{i+1, j} & a_{i+1, j+1} \end{bmatrix}$ 的和，所以，我们可以在每一个元素上面 $\pm$ 一个值 $r$，同时为了保证 $b_{i, j}$ 不变化，所以必然是 $+ 2 \times r$ 和 $- 2 \times r$， 那么操作后的矩阵是这个亚子的： $$\begin{bmatrix} a_{i, j}+r & a_{i, j+1}-r\\ a_{i+1, j}-r & a_{i+1, j+1}+r \end{bmatrix}$$ 又由于我们需要维护整个 $B$，所以我们拓展到整个矩阵： $$\begin{bmatrix} a_{1, 1}+r & a_{1, 2}-r & ... & a_{1, n-1}+r \times (-1)^{n-2} & a_{1, n}+r \times (-1)^{n-1}\\ a_{2, 1}+r & a_{2, 2}-r & ... & a_{2, n-1}+r \times (-1)^{n-2} & a_{2, n}+r \times (-1)^{n-1}\\ ... & ... & ... & ... & ...\\ a_{n-1, 1}+r & a_{n-1, 2}-r & ... & a_{n-1, n-1}+r \times (-1)^{n-2} & a_{n-1, n}+r \times (-1)^{n-1}\\ a_{n, 1}+r & a_{n, 2}-r & ... & a_{n, n-1}+r \times (-1)^{n-2} & a_{n, n}+r \times (-1)^{n-1} \end{bmatrix}$$ 这时候就可以猜个性质：对某一行交替 $+r,-r,+r,-r$ 后对 $B$ 没有影响。 同理列也一致。 证明的话，对于任意的 $b_{i, j}$ 由于加减是交替的，所以 $new\ b_{i, j}=b_{i, j} +r -r =b_{i, j}$，回到了最初的值。 那我们就设第 $i$ 行的 $r$ 是 $dis_i$ ，第 $j$ 列的 $r$ 是 $dis_{n+j}$，由于这样的话某几行/列就是 $a_{i, j}+dis_i+dis_{n+j}$，那么我们重设 $dis_i=(-1)^i \times dis_i, dis_{j+n}=(-1)^{j+1} \times dis_{j+n}$ 后，矩阵不管那一行/列，就都能满足差分约束的板子了。 ### Code ``` #include <stdio.h> #include <algorithm> #include <string.h> #include <queue> #include <vector> using namespace std; typedef long long ll; const int N=305; const int L=0; const int R=1e6; const int INF=0x3f3f3f3f; inline int read(){ char ch=getchar();int x=0, f=1; while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } int n, m, a[N][N], b[N][N]; ll dis[N<<1]; vector < pair <int, int> > G[N<<1]; struct StPh{ int cnt[N<<1]; bool in[N<<1]; queue <int> Q; void clear(){ memset(cnt, 0, sizeof(cnt)); memset(in, 0, sizeof(in)); while(!Q.empty()) Q.pop(); } bool spfa(){ dis[1]=0, Q.push(1); while(!Q.empty()){ int x=Q.front();Q.pop();in[x]=0, cnt[x]++; if(cnt[x]>n+m) return 1; int sz=(int)G[x].size(); for(int i=0; i<sz; i++){ int to=G[x][i].first, w=G[x][i].second; if(dis[to]>dis[x]+w){ dis[to]=dis[x]+w; if(!in[to]) Q.push(to), in[to]=1; } } } return 0; } }stph; void clear(){ memset(a, 0, sizeof(a)); memset(dis, 9, sizeof(dis)); for(int i=1; i<=n+m; i++) G[i].clear(); stph.clear(); } int solve(){ n=read(), m=read(); clear(); for(int i=1; i<n; i++) for(int j=1; j<m; j++) b[i][j]=read(); for(int i=n; i; i--) for(int j=m; j; j--) a[i][j]=b[i][j]-a[i+1][j]-a[i+1][j+1]-a[i][j+1]; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){ if((i+j)&1) G[j+n].push_back(make_pair(i, a[i][j])), G[i].push_back(make_pair(j+n, 1e6-a[i][j])); else G[j+n].push_back(make_pair(i, 1e6-a[i][j])), G[i].push_back(make_pair(j+n, a[i][j])); } if(stph.spfa()) return 0*printf("NO\n"); printf("YES\n"); for(int i=1; i<=n; i++, puts("")) for(int j=1; j<=m; j++){ a[i][j]+=(((i+j)&1)?-1:1)*dis[i]; a[i][j]+=(((i+j)&1)?1:-1)*dis[j+n]; printf("%d ", a[i][j]); } return 0; } signed main(){ int T=read(); for(; T; T--) solve(); return 0; } ```