Codechef March Challenge 2021 Div2 Consecutive Adding(CONSADD)

Codechef March Challenge 2021 Div2 Consecutive Adding(CONSADD)

题目大意：

给定两个(n imes m)矩阵(A)，(B)和一个常数(x)

现在对于(A)操作，每次可以选择一行或者一列连续的(x)个，一起改变同一个数值(vin )

判断是否可以由(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))判定

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");
	}
}