原题：https://ac.nowcoder.com/acm/contest/7501/J
大致题意：给你一个n x m的矩阵，我们可以对其中任意一个a x b的矩阵进行操作（所有元素减一）。可以进行无限次操作，每次可以选任意一个a x b的矩阵。 求问是否可以让n x m的矩阵内的所有元素为零
思路：
对于nxm的矩阵，从左上角第一个元素in[1][1]开始，如果要让nxm的矩阵所有元素为零，那么在in[1][1]上必须进行in[1][1]次操作，而对in[1][1]可进行操作的axb的矩阵是唯一的。
处理完in[1][1]后，我们需要记录从1 1 到a b这个矩阵内已经减掉了in[1][1]这个事实。所以我们可以用一个二维数据deduct[i][j]来记录当前ij点上的在之前的操作中删去的个数。
deduct在遍历的过程中转化为前缀和。而当在ab范围内减去一个数字的时候进行差分。
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 typedef long long ll; 5 const int mx=1e3+10; 6 ll deduct[mx][mx], in[mx][mx]; 7 int main(){ 8 ll T, n, m, a, b; 9 scanf("%lld", &T); 10 for(ll lp=1;lp<=T;lp++){ 11 scanf("%lld %lld %lld %lld", &n, &m, &a, &b); 12 for(ll i=1;i<=n;i++) { 13 for (ll j = 1; j <= m; j++) 14 scanf("%lld", &in[i][j]); 15 } 16 memset(deduct, 0, sizeof(deduct)); 17 bool ok=true; 18 for(ll i=1;i<=n&&ok;i++){ 19 for(ll j=1;j<=m&&ok;j++){ 20 deduct[i][j]+=deduct[i-1][j]+deduct[i][j-1]-deduct[i-1][j-1]; 21 //求前缀和 22 if(deduct[i][j]>in[i][j]){//如果已经减去的数量比当前的数值大了 不可能为0 23 ok=false; 24 break; 25 } 26 else if(deduct[i][j]<in[i][j]){//如果比当前的数量小 意味着还要继续减 27 ll t=in[i][j]-deduct[i][j]; 28 if(i+a-1>n||j+b-1>m){ 29 ok=false; 30 break; 31 } 32 //差分 33 //当前的减了 axb范围内的数据都要减 34 deduct[i][j]+=t, deduct[i+a][j+b]+=t; 35 deduct[i+a][j]-=t, deduct[i][j+b]-=t; 36 } 37 } 38 } 39 printf("%s\n", ok?"^_^":"QAQ"); 40 } 41 return 0; 42 }