Codechef March Challenge 2021 Div2 Consecutive Adding(CONSADD)
题目大意:
给定两个n×m矩阵A,B和一个常数x
现在对于A操作,每次可以选择一行或者一列连续的x个,一起改变同一个数值v∈\Z
判断是否可以由A变成B
显然可以先将A,B作差,转化为操作成0矩阵
进一步,我们将A矩阵行内差分,使得每次行操作变为一个单点Ai,j+v,一个单点Ai,j+x−v
在此基础上,继续差分即可将行列操作都转化为单点操作
此时容易发现,Ai,j的数值有关联的部分都是Ai,j,Ai+x,j,Ai,j+x⋯Ai+ax,j+bx
也就是相差x的,考虑可以将这一部分子矩形提取出来,这样问题变成了
每次操作一个数Ai,j+v,可以选择相邻一个数Ai,j+1或Ai+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]; 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"); } }
|