acwing796 子矩阵的和

题目地址

https://www.acwing.com/problem/content/798/

思路

照搬题解的图。

维护s[i][j]数组用于存储矩阵点和其左上角的值，则求某一点的前缀和为：

黄色框减去两个紫框加上补回重叠部分的框。

即S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

此外，s[i][j]可以用递推方式求出，即

紫框加紫框补回重叠的橙框加上x2,y2的值

AC代码

#include <iostream>
using namespace std;
int n, m, q;
int a[1001][1001];
int s[1001][1001];
int ans(int x1,int y1,int x2,int y2)
{
	return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}
int main(int argc, char* argv[])
{
	/*S[i, j] = 第i行j列格子左上部分所有元素的和
	以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
	S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]*/
	cin >> n >> m >> q;

	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin >> a[i][j];
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
		}
	}
	int x1, x2, y1, y2;
	while (q--)
	{
		cin >> x1 >> y1 >> x2 >> y2;
		cout << ans(x1, y1, x2, y2) << endl;
	}
	return 0;
}

           

心得

本来以为是简单题，结果白给。明天要写什么题未知，看好多题都好难不想写哇哇哇哇