当前位置:首页 > 差分约束 > 正文
洛谷P7515[省选联考2021A卷]矩阵游戏
181+

题目大意:已知n*m的矩阵每个2*2方阵四个元素的和,请还原出这个矩阵。

题目描述

Alice 有一个 $n \times m$ 的矩阵 $a_{i, j}$($1 \le i \le n$,$1 \le j \le m$),其每个元素为大小不超过 ${10}^6$ 的非负整数。

Bob 根据该矩阵生成了一个 $(n – 1) \times (m – 1)$ 的矩阵 $b_{i, j}$($1 \le i \le n – 1$,$1 \le j \le m – 1$),每个元素的生成公式为

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

现在 Alice 忘记了矩阵 $a_{i, j}$,请你根据 Bob 给出的矩阵 $b_{i, j}$ 还原出 $a_{i, j}$。

输入输出格式

输入格式

**本题有多组数据。**

第一行,一个整数 $T$,表示数据组数。对于每组数据:

第一行,两个正整数 $n, m$,表示矩阵 $a_{i, j}$ 的大小。
接下来 $n – 1$ 行,每行 $m – 1$ 个非负整数,表示 $b_{i, j}$。

输出格式

对于每组数据:

1. 若矩阵 $b_{i, j}$ 无法被生成,则输出一行一个字符串 `NO`。
2. 若矩阵 $b_{i, j}$ 可被生成,则先输出一行一个字符串 `YES`,接下来输出 $n$ 行每行 $m$ 个(用单个空格分隔的)大小不超过 ${10}^6$ 的非负整数表示 $a_{i, j}$。

若有多个矩阵 $a_{i, j}$ 可生成给出的 $b_{i, j}$,输出其中任意一个即可。

输入输出样例

输入样例 #1

3
3 3
28 25
24 25
3 3
15 14
14 12
3 3
0 3000005
0 0

输出样例 #1

YES
7 8 8
8 5 4
4 7 9
YES
4 2 2
5 4 6
5 0 2
NO

说明

**【数据范围】**

对于所有测试数据:$1 \le T \le 10$,$2 \le n, m \le 300$,$0 \le b_{i, j} \le 4 \times {10}^6$。

每个测试点的具体限制见下表:

测试点编号 特殊限制

解题思路

暴力:对于只有两列的情况,我们可以枚举第一行的和,递推后面行的和,只要和满足条件,就能分成两半,填出矩阵a。

一个2*2的方阵,只要确定其中3个元素,另一个也就定下来了。我们不妨设第一行第一列的元素的值为0,这样就可以填出一个矩阵a,满足矩阵b的限制。那么,怎样才可以满足0~1e6的限制呢?

如果$a_{11}$不满足条件,太小了我们可以加一个数,相邻的交替加减即可。如果同一行的数字都要加怎么办?那只能列进行减,也是交替解决。

+x1 -x1 +x1 -x1 +x1      +y1 +y2 +y3 +y4 +y5 
+x2 -x2 +x2 -x2 +x2      -y1 -y2 -y3 -y4 -y5 
+x3 -x3 +x3 -x3 +x3      +y1 +y2 +y3 +y4 +y5 
+x4 -x4 +x4 -x4 +x4      -y1 -y2 -y3 -y4 -y5 
+x5 -x5 +x5 -x5 +x5      +y1 +y2 +y3 +y4 +y5

第一行依次$+x_1、-x_1、+x_1$……;第一列依次$+y_1、-y_1、+y_1$……

这样,要让$a_{11}$满足条件,只需要满足$0 <= a_{11}+x_1+y_1 <= 1e6$,简单来说就是0 <= a +x + y <= 1e6,即x <= -x + 1e6 – a和-x <= y+a。

x和-x的关系很难描述,我们可以稍微调整一下,让其中x和y异号:

+x1 -x1 +x1 -x1 +x1      -y1 +y2 -y3 +y4 -y5 
-x2 +x2 -x2 +x2 -x2      +y1 -y2 +y3 -y4 +y5 
+x3 -x3 +x3 -x3 +x3      -y1 +y2 -y3 +y4 -y5 
-x4 +x4 -x4 +x4 -x4      +y1 -y2 +y3 -y4 +y5 
+x5 -x5 +x5 -x5 +x5      -y1 +y2 -y3 +y4 -y5

这样,每个位置的约束,要么是0 <= a+x-y <= 1e6,要么是0 <= a-x+y <= 1e6,可以转成x <= y+1e6-a和y <= x+a。我们可以当差分约束系统来做。

x编号1到n,y编号n+1到n+m,用Bell-man Ford算法,松弛n+m次必出结果。如果矩阵元素下标i+j是奇数,那么对于被减的变量x,有f[x] = min(f[x], y+a),对于加数y,有f[y] = min(f[y], x+1e6-a);如果i+j是奇数,则x和y反过来。如果松弛不出来则无解。另外,为了防止爆int,如果x或者y的值太小,可以直接判断无解,因为没必要某一行或者某一列减太多。

程序实现

洛谷P7515[省选联考2021A卷]矩阵游戏:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter