二维前缀和公式 AcWing 796. 子矩阵的和

这篇具有很好参考价值的文章主要介绍了二维前缀和公式 AcWing 796. 子矩阵的和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

#include<bits/stdc++.h>

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++)
            cin>>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;
        cin>>x1>>y1>>x2>>y2;
        cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
    }
    
    return 0;
}

二维前缀和

记住两个公式就行

不知道算难还是算简单,公式就是代码里面写的那样,完完全全公式,没有任何其他东西文章来源地址https://www.toymoban.com/news/detail-826221.html

到了这里,关于二维前缀和公式 AcWing 796. 子矩阵的和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 利用前缀和计算二维矩阵子矩阵的和

    作者简介 :一名后端开发人员,每天分享后端开发以及人工智能相关技术,行业前沿信息,面试宝典。 座右铭 :未来是不可确定的,慢慢来是最快的。 个人主页 :极客李华-CSDN博客 合作方式 :私聊+ 这个专栏内容 :用最低价格鼓励和博主一起在寒假打卡高频大厂算法题,

    2024年04月17日
    浏览(45)
  • 二维矩阵的前缀和+子矩阵的和-java

    二维矩阵的前缀和,我们可以通过求前缀和来把求二维矩阵的求某一块的和,从时间复杂度O(n^2)变成O(1)常数级,大大降低了时间复杂度 文章目录 前言 一、二维矩阵的前缀和应该怎么做? 1.引入一个二维数组 2.二维前缀和矩阵数组 3.推出二维矩阵前缀和的公式计算 3.1 代码如

    2024年03月27日
    浏览(102)
  • C++ 二维前缀和 子矩阵的和

    输入一个 n 行 m 列的整数矩阵,再输入 q 个询问,每个询问包含四个整数 x1,y1,x2,y2 ,表示一个子矩阵的左上角坐标和右下角坐标。 对于每个询问输出子矩阵中所有数的和。 输入格式 第一行包含三个整数 n,m,q 。 接下来 n 行,每行包含 m 个整数,表示整数矩阵。 接下来

    2024年02月21日
    浏览(54)
  • 【算法 | 模拟No.4】AcWing 756. 蛇形矩阵 & AcWing 40. 顺时针打印矩阵

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【AcWing算法提高学习专栏】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成

    2024年01月16日
    浏览(54)
  • AcWing算法提高课-1.3.11二维费用的背包问题

    点这里 题目描述 有 N N N 件物品和一个容量是 V V V 的背包,背包能承受的最大重量是 M M M 。 每件物品只能用一次。体积是 v i v_i v i ​ ,重量是 m i m_i m i ​ ,价值是 w i w_i w i ​ 。 求解将哪些物品装入背包,可使物品总体积不超过背包容量,总重量不超过背包可承受的最大

    2024年02月06日
    浏览(49)
  • 796. 子矩阵的和

    Problem: 796. 子矩阵的和 这是一个二维前缀和的问题。二维前缀和的主要思想是预处理出一个二维数组,使得每个位置(i, j)上的值表示原数组中从(0, 0)到(i, j)形成的子矩阵中所有元素的和。这样,对于任意的子矩阵(x1, y1)到(x2, y2),我们可以通过四个前缀和的值快速计算出其和。

    2024年02月22日
    浏览(43)
  • 【每日挠头算法题】Acwing 756. 蛇形矩阵 —— 巧妙解法

    👑作者主页:@进击的安度因 🏠学习社区:进击的安度因(个人社区) 📖专栏链接:每日挠头算法题 如果无聊的话,就来逛逛 我的博客栈 吧! 🌹 链接 :756. 蛇形矩阵 输入两个整数 n 和 m ,输出一个 n 行 m 列的矩阵,将数字 1 到 n × m 按照回字蛇形填充至矩阵中。 具体矩

    2024年02月02日
    浏览(46)
  • AcWing 102:最佳牛围栏 ← 二分+前缀和

    【题目来源】 https://www.acwing.com/problem/content/104/ 【题目描述】 农夫约翰的农场由 N 块田地组成,每块地里都有一定数量的牛,其数量不会少于 1 头,也不会超过 2000 头。 约翰希望用围栏将一部分连续的田地围起来,并使得围起来的区域内每块地包含的牛的数量的平均值达到

    2024年01月20日
    浏览(40)
  • 【第二十五课】动态规划:完全背包问题(acwing-3 / 公式推导 / 思路理解 / 优化 / c++代码)

    目录 思路 朴素代码 优化 公式推导上  二维代码  一维代码 公式理解上   在开始看完全背包问题之前,可能需要先了解01背包及其解决办法。 指路👇 【第二十五课】动态规划:01背包问题(acwing-2 / 思路 / 含一维数组优化 / c++代码) 这个问题和01背包的区别就是 每件物品可以

    2024年03月19日
    浏览(63)
  • AcWing 753、754、755平方矩阵

    1.题目 输入整数 N,输出一个 N 阶的回字形二维数组。 数组的最外层为 1,次外层为 2,以此类推。 输入格式 输入包含多行,每行包含一个整数 N。 当输入行为 N=0时,表示输入结束,且该行无需作任何处理。 输出格式 对于每个输入整数 N,输出一个满足要求的 N阶二维数组。

    2024年02月03日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包