Codechef March Challenge 2021 Div2 Consecutive Adding(CONSADD)

题目大意：

给定两个$n\times m$矩阵$A$，$B$和一个常数$x$

现在对于$A$操作，每次可以选择一行或者一列连续的$x$个，一起改变同一个数值$v\in \Z$

判断是否可以由$A$变成$B$


显然可以先将$A,B$作差，转化为操作成0矩阵

进一步，我们将$A$矩阵行内差分，使得每次行操作变为一个单点$A_{i,j}+v$，一个单点$A_{i,j+x}-v$

在此基础上，继续差分即可将行列操作都转化为单点操作

此时容易发现，$A_{i,j}$的数值有关联的部分都是$A_{i,j},A_{i+x,j},A_{i,j+x}\cdots A_{i+ax,j+bx}$

也就是相差$x$的，考虑可以将这一部分子矩形提取出来，这样问题变成了

每次操作一个数$A_{i,j}+v$，可以选择相邻一个数$A_{i,j+1}$或$A_{i+1,j}$去$-v$

对于每个这样的子问题，容易发现有解的充要条件：子矩阵元素和为0

（可以依次考虑每个元素贪心构造方案）

如此可以$O(nm)$判定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

const int N=1010,INF=1e9+10;

int n,m,k;
ll A[N][N],B[N][N];
int V[N][N];

int main(){
	rep(kase,1,rd()) {
		n=rd(),m=rd(),k=rd();
		rep(i,1,n+1) rep(j,1,m+1) A[i][j]=V[i][j]=0;
		rep(i,1,n) rep(j,1,m) A[i][j]=rd();
		rep(i,1,n) rep(j,1,m) A[i][j]-=rd();
		rep(i,1,n+1) drep(j,m+1,1) A[i][j]-=A[i][j-1];
		drep(i,n+1,1) rep(j,1,m+1) A[i][j]-=A[i-1][j];
        // 3 次作差
		int f=1;
		rep(i,1,n+1) rep(j,1,m+1) if(!V[i][j]) {
			ll s=0;
            // 子问题判定
			for(int a=i;a<=n+1;a+=k) for(int b=j;b<=m+1;b+=k) {
				V[a][b]=1;
				s+=A[a][b];
			}
			f&=s==0;
		}
		puts(f?"Yes":"No");
	}
}