《洛谷深入浅出进阶篇》P3397 地毯————二维差分

上链接:P3397 地毯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)icon-default.png?t=N7T8https://www.luogu.com.cn/problem/P3397

上题干:

题目描述

在 n×n 的格子上有 m 个地毯。

给出这些地毯的信息,问每个点被多少个地毯覆盖。

输入格式

第一行,两个正整数 n,m。意义如题所述。

接下来 m 行,每行两个坐标 (x1​,y1​) 和 (x2​,y2​),代表一块地毯,左上角是 (x1​,y1​),右下角是(x2​,y2​)。

输出格式

输出 n 行,每行 n 个正整数。

第 i 行第 j 列的正整数表示 (i,j) 这个格子被多少个地毯覆盖。

输入输出样例

输入 #1复制

5 3
2 2 3 3
3 3 5 5
1 2 1 4

输出 #1复制

0 1 1 1 0
0 1 1 0 0
0 1 2 1 1
0 0 1 1 1
0 0 1 1 1

说明/提示

样例解释

覆盖第一个地毯后:

00000
01100
01100
00000
00000

覆盖第一、二个地毯后:

00000
01100
01211
00111
00111

覆盖所有地毯后:

01110
01100
01211
00111
00111

数据范围

对于 20% 的数据,有 n≤50,m≤100。

对于 100% 的数据,有 n,m≤1000。

在上一篇已经讲过了差分是什么,和一维差分:

《洛谷深入浅出进阶篇》 P2367语文成绩——差分-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/louisdlee/article/details/134400596 这章的内容来介绍一下,二维差分。

假设b[i,j]为差分数组,a[i,j]为原数组

b[i,j]和a[i,j]满足下面这个性质:

 \sum_{i=1}^{n}\sum_{j=1}^{m}b_{i,j}=a_{i,j}

(只要是差分就应该满足这个性质)

但是根据题目的不同,差分数组的求法也有所不同

但是我们求答案的时候一定要记住四个字:前加后减

给大家举几个例子理解:

假设这是第一块地毯(原数组),

12345
21100
31100
40000
50000

那么它的差分数组可以是这样的。

12345
210-10
310-10
40000
50000

假设这是第二块地毯:

00000
00000
00111
00111
00111

那么它的差分数组我想你们应该可以想到了吧:(加了一列虚拟边界来表示,其实我们真实遍历的时候不会扫描到n*m之外的格子)

123456
200000
30100-1
40100

-1

50100-1

 我们发现:

-1的位置都是在原来矩阵的后面一列,

假设左上角为(x1,y1) 右下角为(x2,y2)

那么第一列的-1应该在 (x1,y2+1)处

第二列的-1应该在(x1+1,y2+1)处

因为我们加了虚拟边界,当-1出现在原来的边界外的时候,也不用担心。

上代码:

const int N = 1e3 + 10;
int a[N][N];
int b[N][N];
int main()
{int n, m;cin >> n >> m;while (m--) {int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;for (int i = x1; i <= x2; i++){b[i][y1]++;b[i][y2 + 1]--;}}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){b[i][j] += b[i][j - 1];cout << b[i][j] << ' ';}cout << endl;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/193778.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

浅尝:iOS的CoreGraphics和Flutter的Canvas

iOS的CoreGraphic 基本就是创建一个自定义的UIView&#xff0c;然后重写drawRect方法&#xff0c;在此方法里使用UIGraphicsGetCurrentContext()来绘制目标图形和样式 #import <UIKit/UIKit.h>interface MyGraphicView : UIView endimplementation MyGraphicView// Onl…

桌面云架构讲解(VDI、IDV、VOI/TCI、RDS)

目录 云桌面架构 VDI 虚拟桌面基础架构 IDV 智能桌面虚拟化 VOI/TCI VOI 虚拟系统架构 TCI 透明计算机架构 RDS 远程桌面服务 不同厂商云桌面架构 桌面传输协议 什么是云桌面 桌面云是虚拟化技术成熟后发展起来的一种应用&#xff0c;桌面云通常也称为云桌面、VDI等 …

Flink(五)【DataStream 转换算子(上)】

前言 这节注定是一个大的章节&#xff0c;我预估一下得两三天&#xff0c;涉及到的一些东西不懂就重新学&#xff0c;比如 Lambda 表达式&#xff0c;我只知道 Scala 中很方便&#xff0c;但在 Java 中有点发怵了&#xff1b;一个接口能不能 new 来构造对象? 答案是可以的&…

代码随想录 Day47 动态规划15 LeetCode T583 两个字符串的删除操作 T72 编辑距离

LeetCode T583 两个字符串的删除操作 题目链接:583. 两个字符串的删除操作 - 力扣&#xff08;LeetCode&#xff09; 题目思路: 本题有两个思路 1.使用两个字符串的长度之和-2*最长公共子串(换汤不换药) 代码随想录Day45 动态规划13 LeetCode T1143最长公共子序列 T1135 不相交…

跨国企业如何选择安全靠谱的跨国传输文件软件?

随着全球化的不断发展&#xff0c;跨国企业之间的合作变得越来越频繁。而在这种合作中&#xff0c;如何安全、可靠地将文件传输给合作伙伴或客户&#xff0c;成为了跨国企业必须面对的问题。 然而&#xff0c;跨国文件传输并不是一件容易的事情&#xff0c;由于网络物理条件的…

OpenCV入门4——实现图形的绘制

文章目录 OpenCV绘制直线OpenCV绘制矩形和圆画矩形画圆 OpenCV椭圆的绘制OpenCV绘制多边形OpenCV绘制文本实现鼠标绘制基本图形 OpenCV绘制直线 # -*- coding: utf-8 -*- import cv2 import numpy as npimg np.zeros((480, 640, 3), np.uint8) # 坐标点为(x, y) cv2.line(img,…

《视觉SLAM十四讲》-- 后端 1(下)

8.2 BA 与图优化 Bundle Adjustment 是指从视觉图像中提炼出最优的 3D 模型和相机参数&#xff08;内参和外参&#xff09;。 8.2.1 相机模型和 BA 代价函数 我们从一个世界坐标系中的点 p \boldsymbol{p} p 出发&#xff0c;把相机的内外参数和畸变都考虑进来&#xff0c;…

C语言从入门到精通之【char类型】

char类型用于储存字符&#xff08;如&#xff0c;字母或标点符号&#xff09;&#xff0c;但是从技术层面看&#xff0c;char是整数类型。因为char类型实际上储存的是整数而不是字符。计算机使用数字编码来处理字符&#xff0c;即用特定的整数表示特定的字符。 char类型占1个字…

wx.canvasToTempFilePath生成图片保存到相册

微信小程序保存当前画布指定区域的内容导出生成指定大小的图片&#xff0c;记录一下 api&#xff1a;wx.canvasToTempFilePath 效果&#xff1a; 代码&#xff1a;wxml <canvas style"width: {{screenWidth}}px; height: {{canvasHeight}}px;" canvas-id"my…

NewStarCTF2023 Week3 Reverse方向 题目STL WP

分析 代码不多&#xff0c;逻辑挺清楚的。 先用Z3解出V7&#xff1a; from z3 import *s Solver() v1, v2, v3, v4, v5, v6 BitVecs(v1 v2 v3 v4 v5 v6, 32) v7, v8, v9, v10, v11 BitVecs(v7 v8 v9 v10 v11, 32)s.add((v1 << 15) ^ v1 0x2882D802120E) s.add((v2 …

借助拧紧曲线高效管理螺栓装配防错——SunTorque智能扭矩系统

拧紧曲线作为拧紧质量的“晴雨表”&#xff0c;在拧紧过程中&#xff0c;能够实时探知到拧紧状态是否存在异常&#xff0c;并根据曲线特质推测出拧紧过程中遇到了什么样的问题&#xff0c;今天SunTorque智能扭矩系统带您了解拧紧曲线在螺栓装配防错管理中如何发挥作用。 合格的…

搭建知识付费系统的最佳实践是什么

在数字化时代&#xff0c;搭建一个高效且用户友好的知识付费系统是许多创业者和内容创作者追求的目标。本文将介绍一些搭建知识付费系统的最佳实践&#xff0c;同时提供一些基本的技术代码示例&#xff0c;以帮助你快速入门。 1. 选择合适的技术栈&#xff1a; 搭建知识付费…

论文阅读:YOLOV: Making Still Image Object Detectors Great at Video Object Detection

发表时间&#xff1a;2023年3月5日 论文地址&#xff1a;https://arxiv.org/abs/2208.09686 项目地址&#xff1a;https://github.com/YuHengsss/YOLOV 视频物体检测&#xff08;VID&#xff09;具有挑战性&#xff0c;因为物体外观的高度变化以及一些帧的不同恶化。有利的信息…

GitHub Universe 2023:AI 技术引领软件开发创新浪潮

GitHub 是全球领先的软件开发和协作平台&#xff0c;数百万开发者和企业在此分享、学习和创建卓越的软件。同时 GitHub 处在 AI 技术前沿&#xff0c;通过其先进的 AI 技术增强开发者体验并赋能未来软件开发的使命。在今天的文章中&#xff0c;我们将一起看看在 GitHub 年度大会…

Python---数据序列类型之间的相互转换

list()方法&#xff1a;把某个序列类型的数据转化为列表 # 1、定义元组类型的序列 tuple1 (10, 20, 30) print(list(tuple1))# 2、定义一个集合类型的序列 set1 {a, b, c, d} print(list(set1))# 3、定义一个字典 dict1 {name:刘备, age:18, address:蜀中} print(list(dict1…

沉浸式航天vr科普馆VR太空主题馆展示

科普教育从小做起&#xff0c;现在我们的很多地方小孩子游乐体验不单单只有草坪玩耍体验&#xff0c;还有很多科普知识的体验馆和游玩馆。虽然现在我们还不能真实的上太空或者潜入海底&#xff0c;但是这些现在已经可以逼真的展示在我们面前。通过一种虚拟现实技术手段。人们带…

PON网络是什么

上节介绍到PON网络概念&#xff0c;PON网络具备节省局端光缆资源、避免故障点的同时&#xff0c;还具备拥有更远的传输距离、更高的带宽以及分光特性&#xff08;P2MP&#xff09;的优势。 PON&#xff08;无源光纤网络&#xff0c;Passive Optical Network&#xff09;网络&am…

基于单片机的智能家居安保系统(论文+源码)

1.系统设计 本次基于单片机的智能家居安保系统设计&#xff0c;在功能上如下&#xff1a; 1&#xff09;以51单片机为系统控制核心&#xff1b; 2&#xff09;温度传感器、人体红外静释电、烟雾传感器来实现检测目的&#xff1b; 3&#xff09;以GSM模块辅以按键来实现远/近程…

【阿里云】函数计算 X 通义千问快速部署

写在前面&#xff1a;博主是一只经过实战开发历练后投身培训事业的“小山猪”&#xff0c;昵称取自动画片《狮子王》中的“彭彭”&#xff0c;总是以乐观、积极的心态对待周边的事物。本人的技术路线从Java全栈工程师一路奔向大数据开发、数据挖掘领域&#xff0c;如今终有小成…

从能用到好用,国产CPU不是你想象中的样子了?

最近看到了挺多关于国产CPU的评测视频&#xff0c;主要测试了鲲鹏、飞腾、海光、龙芯这四家。作为信创从业者&#xff0c;也想结合日常工作中接触到的国产CPU使用体验&#xff0c;发表些自己的看法。 我看到的评测&#xff0c;主要是采用SPEC CPU2006进行横向对比。SPEC CPU20…