AcWing 796. 子矩阵的和

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 796. 子矩阵的和原题链接简单

作者：

番茄酱 , 2019-08-13 18:05:41 , 所有人可见 , 阅读 25907

265

122

二维前缀和

二维前缀和1.png 二维前缀和2.png

$S[i,j]$ 即为图1红框中所有数的的和为：

$S[i,j]=S[i,j-1]+S[i-1,j]-S[i-1,j-1]+a[i,j]$
$(x_1,y_1),(x_2,y_2)$ 这一子矩阵中的所有数之和为： $S[x_2,y_2]-S[x_1-1,y_2]-S[x_2,y_1-1]+S[x_1-1,y_1-1]$

代码：

#include <iostream>

using namespace std;

const int N = 1010;

int a[N][N], s[N][N];

int main() {
    int n, m, q;
    cin >> n >> m >> q;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            s[i][j] = s[i][j - 1] + s[i - 1][j] - 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]); 
    }

    return 0;
}

58 评论

笨死了 2023-03-20 12:34

学习总结了一、二维前缀和差分，希望对你有帮助~
https://blog.csdn.net/m0_74215326/article/details/129620912?spm=1001.2014.3001.5502

暴揍女朋友 2023-03-30 20:09

看完回来的，理解很透彻，非常厉害的一篇题解！！

海绵宝宝顶嘴先生 2023-04-02 17:49 回复了暴揍女朋友的评论

看完你的评论去看的的确不错

末流211选手 2023-01-04 16:08

还是错的，原代码按上去了

QiYao 2023-01-05 21:25

没啥问题呀，很清晰。谢谢大佬～

June_1 2022-07-04 10:04

我咋还是超时呢

Littlecat 2022-03-23 18:26

愚钝的我终于懂了

高木 2024-04-08 20:42

666

xyj23 2022-07-19 19:00

咋还是错的…大佬们帮忙看看啊

#include<iostream>
#include<cstdio>
using namespace std;
int a[1001][1001],x1[200010],y1[200010],x2[200010],y2[200010],d[1001][1001];
int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    for(int i = 0;i < n;i ++){
        for(int j = 0;j < m;j ++){
            cin>>a[i][j];d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+a[i][j];
        }
    }

    for(int i = 0;i < q;i ++)
    {
        cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
        cout<<d[x2[i]-1][y2[i]-1]+d[x1[i]-2][y1[i]-2]-d[x1[i]-2][y2[i]-1]-d[x2[i]-1][y1[i]-2]<<endl;
    }
    return 0;
}

xyj23 2022-07-19 19:01

感觉没问题了啊。。。最后一个数据总是过不了，Wrong Answer

番茄酱 2022-07-19 22:44 回复了 xyj23 的评论

#include<iostream>
#include<cstdio>
using namespace std;
int a[1001][1001],x1[200010],y1[200010],x2[200010],y2[200010],d[1001][1001];
int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            cin>>a[i][j];d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+a[i][j];
        }
    }

    for(int i = 0;i < q;i ++)
    {
        cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
        cout<<d[x2[i]][y2[i]]+d[x1[i]-1][y1[i]-1]-d[x1[i]-1][y2[i]]-d[x2[i]][y1[i]-1]<<endl;
    }
    return 0;
}

i, j 从1开始枚举啊，不然你i=0, j=0的时候，d[0][0]=d[-1][0]+d[0][-1]-.... 下标都越界了。

xyj23 2022-07-20 17:13 回复了番茄酱的评论

好的谢谢

xyj23 2022-07-20 17:13 回复了 xyj23 的评论

ac了

不刷完课不改名 2022-08-07 11:18

下标越界了- -

余下的只有噪音 2023-02-01 10:57 回复了 xyj23 的评论

超时，改成scanf试一试就行了，数据太多了cin输入的速度太慢了，用scanf快一倍。

三线酒架 2023-10-30 13:22

因为输入数据，x1肯比x2还大

冷却 2022-04-09 13:27

13届原题

南京铺子 2022-04-09 22:08

牛逼

freedom_ 2025-01-23 21:21

good

hfuu1 2024-01-24 20:16

#include[HTML_REMOVED]
using namespace std;

const int N=1010;
int a[N][N];
signed main()
{
int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<=n;i){
for(int j=1;j<=m;j){
cin>>a[i][j];
a[i][j]+=a[i][j-1];
}
}
int x1,x2,y1,y2;
while(q–){
long long sum=0;
cin>>x1>>y1>>x2>>y2;
for(int i=y1;i<=y2;i++){
sum+=(a[i][x2]-a[i][x1-1]);
}
cout<<sum<<endl;
}