洛谷 P3397 地毯 刷题笔记 二维差分矩阵

这篇具有很好参考价值的文章主要介绍了洛谷 P3397 地毯 刷题笔记 二维差分矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

P3397 地毯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

洛谷 P3397 地毯 刷题笔记 二维差分矩阵,算法,c++,数据结构

方法1 欺负数据小  暴力水过

#include<iostream>
using namespace std;
const int N=1010;
int a[N][N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        for(int q=x1;q<=x2;q++){
            for(int w=y1;w<=y2;w++){
                a[q][w]++;
            }
        } 
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<a[i][j]<<' ';
        }
        cout<<endl;
    }
    
    
    return 0;
}

方法2 

前缀和 二维数组差分 

不会差分的建议先去看看一维数组的差分

洛谷 P2367 语文成绩 刷题笔记-CSDN博客

#include<iostream>
using namespace std;
const int N=1010;
int a[N][N],b[N][N];
void add(int x1,int y1,int x2,int y2,int x){
     
    b[x1][y1]+=x;
    b[x1][y2+1]-=x;
    b[x2+1][y1]-=x;
    b[x2+1][y2+1]+=x;
    
}
int n,m;
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        add(a,b,c,d,1);
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
            //扫描缓存池 计算前缀和  

        //看不懂缓存池的先去看一维数组差分

        //上面提到了
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<a[i][j]<<' ';
        }
        cout<<endl;
    }
    return 0;
}

add函数推导

a数组是b数组的前缀和数组,对b数组的b[i][j]的修改,会影响到a数组中从a[i][j]及往后的每一个数。

洛谷 P3397 地毯 刷题笔记 二维差分矩阵,算法,c++,数据结构

二维前缀和推导

洛谷 P3397 地毯 刷题笔记 二维差分矩阵,算法,c++,数据结构文章来源地址https://www.toymoban.com/news/detail-771222.html

到了这里,关于洛谷 P3397 地毯 刷题笔记 二维差分矩阵的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 洛谷题单--算法[2-1] 前缀和、差分与离散化

    目录 0.铺垫学习:p1115最大子段和--前缀和+贪心+DP 1.p1719最大加权矩形--前缀和+贪心+DP+矩阵压缩 原题链接: P1115 最大子段和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 原题: 题目描述 给出一个长度为 n 的序列 a,选出其中连续且非空的一段使得这段和最大。 输入格式 第

    2024年02月22日
    浏览(38)
  • leetcode做题笔记74搜索二维矩阵

    给你一个满足下述两条属性的  m x n  整数矩阵: 每行中的整数从左到右按非递减顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数  target  ,如果  target  在矩阵中,返回  true  ;否则,返回  false  。 本题可直接遍历整个矩阵进行查找 本题考察矩

    2024年02月13日
    浏览(47)
  • C++笔记之初始化二维矩阵的方法

    —— 2023年5月20日 上海 code review!

    2024年02月04日
    浏览(55)
  • 力扣题库刷题笔记73--矩阵置零

    1、题目如下:   2、个人Python代码实现 3、个人Python代码思路         a、声明2个空数组p、q,用于存放值为0的元素matrix[i][j]的下标         b、首先遍历二维数组matrix,找到值为0的元素matrix[i][j],将下标i加入数组p,将下标j加入数组q         c、再次遍历二维数组matrix,如

    2024年02月15日
    浏览(76)
  • 洛谷刷题-【入门2】分支结构

    目录 1.苹果和虫子 题目描述 输入格式 输出格式 输入输出样例 2.数的性质 题目描述 输入格式 输出格式 输入输出样例 3.闰年判断 题目描述 输入格式 输出格式 输入输出样例 4.apples 题目描述 输入格式 输出格式 输入输出样例 5.洛谷团队系统 题目描述 输入格式 输出格式 输入

    2024年01月25日
    浏览(41)
  • 二维差分算法详解

    二维差分模板 给定一个n行m列的矩阵,下标从1开始。接下来有q次操作,每次操作输入5个参数x1, y1, x2, y2, k,表示把以(x1, y1)为左上角,(x2,y2)为右下角的子矩阵的每个元素都加上k。请输出操作后的矩阵。 第一行包含三个整数n,m,q。接下来n行,每行m个整数,代表矩阵的元素。接

    2024年01月20日
    浏览(45)
  • 二维差分详解

    前言 上一期我们分享了一维差分的使用方法,这一期我们将接着上期的内容带大家了解二位差分的使用方法,话不多说,LET’S GO!(上一期链接) 二维差分 二维差分我们可以用于对矩阵区间进行多次操作的题。 二维差分我们还可以采用一维差分的思想,如图假如我们要对区

    2024年02月03日
    浏览(50)
  • 图文详解二维差分

    目录 前言 一、 二维差分的定义 二、二维差分的使用 三、计算二维差分 四、ACWing 798. 差分矩阵 一维+二维前缀和详解 图文详解一维差分 对于一个给定的二维数组 arr,它的二维差分数组 d 中 d[i][j] 可以用如下公式计算 : ① ②  ③  ④ 实际上,上面的公式是通过 二维数组

    2024年02月14日
    浏览(40)
  • 洛谷刷题 | P1706 全排列问题

    按照字典序输出自然数 1 1 1 到 n n n 所有不重复的排列,即 n n n 的全排列,要求所产生的任一数字序列中不允许出现重复的数字。 一个整数 n n n 。 由 1 ∼ n 1 sim n 1 ∼ n 组成的所有不重复的数字序列,每行一个序列。 每个数字保留 5 5 5 个场宽。 样例输入 #1 样例输出 #1 1 ≤

    2024年03月26日
    浏览(45)
  • MATLAB将二维数据生成一维是按列排序,矩阵操作笔记,附代码

    matlab和Fortran二维数组按列优先存储 学习一定要敢想敢做!

    2024年02月07日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包