------------恢复内容开始------------

小米入围赛J题

https://ac.nowcoder.com/acm/contest/7501/J

思路：二维差分

#include <bits/stdc++.h>

using namespace std;

int a[1100][1100], b[1100][1100]; 

int t, n, m, w, r;

void insert(int x1, int y1, int x2, int y2, int c){
	b[x1][y1] += c;
	b[x1][y2+1] -= c;
	b[x2+1][y1] -= c;
	b[x2+1][y2+1] += c;
}

int main()
{
	cin >> t;
	while(t--){    
		memset(b, 0, sizeof(b));
		cin >> n >> m >> w >> r;
		
		int sum = 0;
		for(int i = 1;i <= n; ++ i){
			for(int j = 1;j <= m; ++ j){
				cin >> a[i][j];
				insert(i, j, i, j, a[i][j]);
			} 
		}	
		for(int i = 1;i <= n - w + 1;i ++){
			for(int j = 1;j <= m - r + 1; j ++ ){
				if(b[i][j] > 0)
				insert(i, j, i + w - 1, j + r - 1, -b[i][j]);
			}
		}
		int flag = 1;
		for(int i = 1;i <= n; ++ i){
			for(int j = 1;j <= m; ++ j){
				if(b[i][j]) flag = 0;
			}
		}
		if(flag) puts("^_^");
		else puts("QAQ");
	}
}

　　

------------恢复内容结束------------