长沙微网站制作/搜索引擎广告图片

传送门

很明显从左上角开始消除

左上角$(1,1)$右下角$(a,b)$的矩阵会减$s_{1,1}$次

然后考虑左上角$(1,2)$右下角$(a,b+1)$的矩阵…

这样每次减的都是固定的

变成负数就不合法

二位差分可以$O(1)$操作

在操作的时候同时复原数组

可以在线操作的原因是如果合法,之前的地方都变成0了.

#include <bits/stdc++.h>
using namespace std;
int A[1009][1009],rce[1009][1009];
int main()
{int t; cin >> t;while( t-- ){int n,m,a,b;cin >> n >> m >> a >> b;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&A[i][j] );rce[i][j]=A[i][j]-A[i-1][j]-A[i][j-1]+A[i-1][j-1];}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int x = rce[i][j]+rce[i-1][j]+rce[i][j-1]-rce[i-1][j-1];if( x>0&&i<=n-a+1&&j<=m-b+1 ){rce[i][j]-=x;rce[i+a][j+b]-=x;rce[i+a][j]+=x;rce[i][j+b]+=x;}}int flag=1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if( rce[i][j]!=0 )	flag=0;rce[i][j]=0;}if( flag )	cout << "^_^\n";else	cout << "QAQ\n"; }
}