AcWing 796. 子矩阵的和
原题链接
简单
作者:
Stack456
,
2021-04-24 21:53:35
,
所有人可见
,
阅读 3
差点绕晕了,不过还好理解了
一、求解矩形中的和的计算方法x1, y1, x2, y2
- x2, y2,减去的是x1, y1的左半边和上半边,其中都是对应着x2,y2的数据,所以用到的坐标是x2, y2,一定不会有变化
- x1,y1,用的左边的矩形和是x1 - 1, 上边的数据是 y1 - 1,
- 两者配对之后就是
(x1 - 1, y2)
和(x2, y1 -1)
,无论是谁先减少,结果都一样,所以写的时候只要是岔开写就行了
- 最后是就是+ (x1 - 1,y1 - 1)
二、计算s[i][j]的数值方法
- 这个也是比较简单的,简单分析就行
- 当前坐标点左部分+上部分-重合部分 + 当前坐标得数值部分
- 左部分就是:x-1,j 上部分,变化的就是纵坐标 x,j-1, 重叠的就是和 x-1,j-1, 单独就是i,j;
三、为什么前缀和的需要从1开始呢
- 第一个就是计算从第一个数开始的到目前的所有数值,为了对齐后面的中间任意的两点或者是两数,所以从一开始,和动态规划的下标类似
- 其中有-1,所以是从1开始的
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], s[N][N];
int main()
{
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++ )
scanf("%d", &a[i][j]);
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++ )
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
while (q --)
{
int x1, y1, x2, y2;
scanf("%d%d%d%d",&x1, &y1, &x2, &y2);
printf("%d\n", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);
}
}