P7515 [省选联考 2021 A 卷] 矩阵游戏
Mobius127
·
·
题解
题目传送门
题目大意
有一个 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;
}
```