[杂题] 二维前缀和/差分 | Rabbit House = カフェラテ、カフェモカ、カプチーノ~ = QwQ

2020ICPC・小米网络选拔赛第一场 J 题

比赛链接

给出 $n \times m$ 矩阵，给定 $a, b$ ，在矩阵中任意次选择 $a \times b$ 子矩阵，使其中每个元素均减一，问是否能减成零矩阵。

$T\ (1\le T \le 100)$ 组数据， $n,m,a,b\ (1\le n,m \le 1000, 1\le a\le n, 1\le b\le m)$

对于最左上角的格子，要把它变成零，只能选择以它自己为左上角的子矩阵。这样顺着往下推就好啦，，让每个格子都当一次左上角（注意判定距离边界不要小于 a 或 b 什么的。。）看看最后能不能变成零矩阵就好了 |･ω･｀)

剪枝：若中途出现某点为负值，则直接判定为否 QAQ

~~ 哇这题好水，赶紧来一发暴力。~~T 掉了。。。复杂度多了一层。。

然后以为方法不对就楞推了一个多小时。。。_(:з」∠)_

全程没想到 二维差分 呜呜呜

直接上图：

公式：

	前缀和预处理: s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1]
	前缀和查询: sum[(i, j) to (k, l)] = s[k][l] - s[i-1][l] - s[k][j-1] + s[i-1][j-1]
	差分预处理: d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]
	差分修改: (i, j) to (k, l) + v:
	d[i][j] += v; d[i][l+1] -= v; d[k+1][j] -= v; d[k+1][l+1] += v;

搬运一波官方题解：

Code:

	#include <cstdio>
	#include <iostream>
	#include <cstring>
	#define rep(i,s,t) for(int i=s;i<=t;i++)
	using namespace std;
	const int MAXN = 1010;
	int n, m, a, b, mp[MAXN][MAXN], d[MAXN][MAXN], s[MAXN][MAXN];
	//mp 为原矩阵， d 为差分矩阵， s 为 d 的前缀和，即实时还原矩阵元素。
	void process()
	{
	rep (i, 1, n - a + 1) // 不要超出边界
	rep (j, 1, m - b + 1)
	{
	s[i][j] = d[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
	if (s[i][j] > 0) //s [i][j] 为当前子矩阵右上角的值，子矩阵的每个元素都要减去它。
	{
	d[i][j] -= s[i][j];
	d[i + a][j] += s[i][j];
	d[i][j + b] += s[i][j];
	d[i + a][j + b] -= s[i][j];
	s[i][j] -= s[i][j]; // 更新矩阵实时状态
	}
	else if (s[i][j] < 0) // 剪枝，出现负数直接 QAQ
	{
	printf("QAQ\n");
	return;
	}
	}
	rep (i, 1, n)
	rep (j, 1, m)
	{
	s[i][j] = d[i][j] +s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
	if (s[i][j]) // 判断是否是零矩阵
	{
	printf("QAQ\n");
	return;
	}
	}
	printf("^_^\n");
	}
	int main()
	{
	int T;
	scanf("%d", &T);
	while (T--)
	{
	memset(mp, 0, sizeof(mp));
	memset(d, 0, sizeof(d));
	memset(s, 0, sizeof(s));
	scanf("%d%d%d%d", &n, &m, &a, &b);
	rep (i, 1, n)
	rep (j, 1, m)
	{
	scanf("%d", &mp[i][j]);
	d[i][j] = mp[i][j] + mp[i - 1][j - 1] - mp[i - 1][j] - mp[i][j - 1];
	}
	process();
	}
	return 0;
	}