题目题解 A21361 矩阵

题目题解 A21361 矩阵
题意梳理
设原矩阵为 c[i][j]；给出矩阵 a[i][j]，a[i][j]代表以(i,j)为右下角的2×2子矩阵四个元素之和：a[i][j]=c[i][j]+c[i−1][j]+c[i][j−1]+c[i−1][j−1]其中 i≥2,j≥2；题目给出 a 矩阵，要求还原原矩阵 c；每个 c[i][j]∈[0,P−1]。若有多解，输出字典序最小的矩阵（字典序优先比较行号更小，行相同则列号更小的位置，值越小字典序越小）。题目保证一定有解。

数学公式推导（核心式子）
对原式做变形：c[i][j]=a[i][j]−c[i−1][j]−c[i][j−1]−c[i−1]j−1

第一行 (i=1)、第一列 (j=1) 的元素是自由变量，只要满足最后算出的所有 c[i][j] 在区间 [0,P−1] 之内就合法；
一旦确定了第 1 行全部元素 c[1][1],c[1][2],…,c[1][m]，那么剩下所有位置的值都可以被上面的公式唯一计算出来；
c[1][1] 题目隐含为 0（输入a矩阵第一行第一列是 0）；
c[1][2],c[1][3],…,c[1][m] 是我们可以选择的变量；

字典序最小的条件：优先让靠前的列取尽可能小的值。因此我们依次从小到大枚举 c[1][j]（j从 2 到m），每确定一个c[1][j]，计算出后续所有位置取值的合法取值范围[L[i],R[i]]，只要区间存在合法值就固定当前c[1][j]，继续处理下一列，这就是代码里 DFS 的思路。

合法性约束推导
当固定第 1 行前j列之后，对于每一行i≥2，由递推式：c[i][j]=a[i][j]−c[i−1][j]−c[i][j−1]−c[i−1][j−1]必须满足 0≤c[i][j]≤P−1。

对每个i可以推出此时c[1][j]的取值上下界L[i]和R[i]；
只有全局 max(L[i])≤min(R[i])，当前c[1][j]的取值才合法；
为了字典序最小，我们从小到大尝试k(0≤k≤P−1)，第一个满足条件的k就是c[1][j]的取值，之后递归处理j+1列。

代码思路解析（DFS 部分）

dfs(j)：正在确定第 1 行第j列的值c[1][j]；
枚举k从0到P−1（从小到大枚举，保证字典序最小）：
暂定c[1][j]=k；
遍历每一行i≥2，根据递推公式算出c[i][j]，并且更新每一行后续变量的取值上下限L[i]（下界）、R[i]（上界）；
判断如果max(L[i])≤min(R[i])代表当前选择k可行；
可行就递归dfs(j+1)；

当j=m+1代表第 1 行全部确定完毕，此时整个矩阵c全部可以计算出来，输出矩阵并结束程序；
main函数预处理：
初始化L[i]=0,R[i]=P−1；
c[1][1]=0固定；
启动dfs(2)开始确定第 1 行第 2 列往后的值。

复杂度分析

m≤200，P≤10；每一列最多尝试最多P次；
每一次判断合法性循环n次；总复杂度O(m⋅P⋅n)，200×10×200=4×104，时间完全够用。

样例推演
输入：N=3,M=3,P=3a矩阵：plaintext0 0 0
0 4 5
0 5 3

c[1][1]=0；
dfs 先尝试c[1][2]=0，检验后续所有c[i][j]是否都落在[0,2]：
经过约束判断发现可行；

再确定c[1][3]=2；第 1 行确定为：0,0,2；
根据递推公式依次算出：

c[2][2]…​=a[2][2]−c[1][2]−c[2][1]−c[1][1]=4−0−c[2][1]−0最终得到答案矩阵：plaintext0 0 2
2 2 1
1 0 0

和样例输出完全一致。

关键点总结

问题核心转化：原矩阵完全由第一行决定，我们只需要求解字典序最小的第 1 行；
字典序实现技巧：DFS 的时候从小到大枚举取值，第一个合法解就是字典序最优解，找到答案立刻退出程序；
区间约束：选定c[1][j]之后会对后续每一行的取值产生限制，维护L[i],R[i]判断可行性，避免暴力搜索整个矩阵；
递推公式 c[i][j]=a[i][j]−c[i−1][j]−c[i][j−1]−c[i−1][j−1]是本题的数学根基。

简化理解版思路

只有第一行是自由变量，剩下所有元素都被第一行唯一决定；
为字典序最小，前面的位置优先选尽可能小的数字；
每选定第一行的一个数字，检查后面所有格子是否都能落在0∼P−1；
全部第一行数字选定完毕后，推出整个矩阵并输出。

#include<bits/stdc++.h>
using namespace std
;int n,m,p,L[205],R[205],a[205][205],b[205][205],c[205][205];
void dfs(int j)
{
if(j==m+1)
{
for(int i=2;i<=n;i++)
{
for(int j=2;j<=m;j++)
{
c[i][j]=a[i][j]-c[i-1][j]-c[i][j-1]-c[i-1][j-1];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
printf("%d ",c[i][j]);
}
puts("");
}
exit(0);
}
int l[205],r[205];
for(int i=2;i<=n;i++)l[i]=L[i],r[i]=R[i];
for(int k=0;k<p;k++)
{
c[1][j]=k;
bool flag=1;
if(j>1)
{
for(int i=2;i<=n&&flag;i++)
{
c[i][j]=b[i][j]+((i&1)?1:-1)*c[1][j]+(((j+i)&1)?1:-1)*c[1][1];
if(j&1)
{
if(c[i][j]>=p)flag=0;
else if(c[i][j]<0)L[i]=max(L[i],-c[i][j]);
else R[i]=min(R[i],p-c[i][j]-1);
}
else
{
if(c[i][j]<0)flag=0;
else if(c[i][j]>=p)L[i]=max(L[i],c[i][j]+1-p);
else R[i]=min(R[i],c[i][j]);
}
if(L[i]>R[i])flag=0;c[i][1]=L[i];
}
}
if(flag)dfs(j+1);
for(int i=2;i<=n;i++)L[i]=l[i],R[i]=r[i];
}
}
signed main()
{
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
for(int i=2;i<=n;i++)L[i]=0,R[i]=p-1;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)b[i][j]=a[i][j]-b[i-1][j]-b[i][j-1]-b[i-1][j-1];
dfs(1);
return 0;
}#include<bits/stdc++.h>
using namespace std
;int n,m,p,L[205],R[205],a[205][205],b[205][205],c[205][205];
void dfs(int j)
{
if(j==m+1)
{
for(int i=2;i<=n;i++)
{
for(int j=2;j<=m;j++)
{
c[i][j]=a[i][j]-c[i-1][j]-c[i][j-1]-c[i-1][j-1];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
printf("%d ",c[i][j]);
}
puts("");
}
exit(0);
}
int l[205],r[205];
for(int i=2;i<=n;i++)l[i]=L[i],r[i]=R[i];
for(int k=0;k<p;k++)
{
c[1][j]=k;
bool flag=1;
if(j>1)
{
for(int i=2;i<=n&&flag;i++)
{
c[i][j]=b[i][j]+((i&1)?1:-1)*c[1][j]+(((j+i)&1)?1:-1)*c[1][1];
if(j&1)
{
if(c[i][j]>=p)flag=0;
else if(c[i][j]<0)L[i]=max(L[i],-c[i][j]);
else R[i]=min(R[i],p-c[i][j]-1);
}
else
{
if(c[i][j]<0)flag=0;
else if(c[i][j]>=p)L[i]=max(L[i],c[i][j]+1-p);
else R[i]=min(R[i],c[i][j]);
}
if(L[i]>R[i])flag=0;c[i][1]=L[i];
}
}
if(flag)dfs(j+1);
for(int i=2;i<=n;i++)L[i]=l[i],R[i]=r[i];
}
}
signed main()
{
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
for(int i=2;i<=n;i++)L[i]=0,R[i]=p-1;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)b[i][j]=a[i][j]-b[i-1][j]-b[i][j-1]-b[i-1][j-1];
dfs(1);
return 0;
}