二维差分---基础算法
书接上回
a二维数组是b二维数组的前缀和数组,b二维数组是a二维数组的差分数组,也就是说a[i][j]=b[1][1]+b[1][2] + ......b[i][1] + b[i][2] + ...... b[i][j] ,下图是b的二维数组
如图,当你想要整个矩阵中的一个子矩阵都加上一个C,如果我们将b[x1][x2]加上C,那么a数组右下角所有的区域都会加上C,可是我们只想其中的子矩阵加上C,那么如何解决呢?照猫画虎就行,如下图
b[x2+1][y2]减去C,那么图中青绿色的区域都会减去C,b[x1][y1+1]减去C,那么图中绿色区域都会减去C,很明显这样的操作会对红色区域减去两个C,所以b[x2+1][y2+1]加上C,那么红色区域都会加上C
所以就是
b[x1][x2]+=C
b[x2+1][y2]-=C
b[x1][y1+1]-=C
b[x2+1][y2+1]+=C
很好,根据上一篇文章,可以很容易得到插入函数
题目
题目描述
输入一个n行m列的整数矩阵,再输入q个操作,每个操作包含五个整数x1, y1, x2, y2, c,其中(x1, y1)和(x2, y2)表示一个子矩阵的左上角坐标和右下角坐标。每个操作都要将选中的子矩阵中的每个元素的值加上c。
请你将进行完所有操作后的矩阵输出。
输入格式
第一行包含整数n,m,q。接下来n行,每行包含m个整数,表示整数矩阵。
接下来q行,每行包含5个整数x1, y1, x2, y2, c,表示一个操作。
输出格式
共 n 行,每行 m 个整数,表示所有操作进行完毕后的最终矩阵。数据范围
1≤n,m≤1000,
1≤q≤100000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤c≤1000,
−1000≤矩阵内元素的值≤1000输入样例
3 4 3 1 2 2 1 3 2 2 1 1 1 1 1 1 1 2 2 1 1 3 2 3 2 3 1 3 4 1
输出样例
2 3 4 1 4 3 4 1 2 2 2 2
代码
#include <iostream>using namespace std;const int N = 1010;
int b[N][N];
int a[N][N];int n, m, q;void insert(int x1, int y1, int x2, int y2, int c)
{b[x1][y1] += c;b[x2 + 1][y1] -= c;b[x1][y2 + 1] -= c;b[x2 + 1][y2 + 1] += c;}
int main(void)
{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]);insert(i, j,i,j, a[i][j]);}}while (q--){int x1, y1, x2, y2, c;scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);insert(x1, y1, x2, y2, c);}for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];printf("%d ", b[i][j]);}printf("\n");}return 0;
}
相关文章:
二维差分---基础算法
书接上回 a二维数组是b二维数组的前缀和数组,b二维数组是a二维数组的差分数组,也就是说a[i][j]b[1][1]b[1][2] ......b[i][1] b[i][2] ...... b[i][j] ,下图是b的二维数组 如图,当你想要整个矩阵中的一个子矩阵都加上一个C,如果我们将b[x1][x2]加上C,那么a数组右下角所有的…...
C++之结构体智能指针shared_ptr实例(一百九十四)
简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 人生格言: 人生…...
初出茅庐的小李博客之根据编译时间生成软件版本号
为什么要软件版本号呢? 生成软件版本号是在软件开发和维护过程中非常重要的一项任务,它有很多意义和好处,同时也有多种常见的方法。 标识和追踪:软件版本号是唯一的标识符,用于区分不同版本的软件。这有助于开发人员和…...
“投资教父”熊晓鸽老了,IDG光环不再
作者 | 鸠白 艺馨 排版 | Cathy 监制 | Yoda 出品 | 不二研究 2017年,世界互联网大会上,“投资教父”熊晓鸽问映客的创始人:“今年你们利润能有多少?” 对方笑答:“5个亿吧!” “才五个亿?…...
XEX智能交易所:加密货币衍生品杠杆、期货和期权简介
加密货币衍生品杠杆、期货和期权简介 加密货币衍生品是指通过基于区块链技术的交易平台进行交易的各种金融工具。与传统金融衍生品类似,加密货币衍生品的交易方式是基于预测未来市场价格变动的套利策略。接下来将具体介绍不同类型的加密货币衍生品以及风险。 加密…...
记录第一次带后端团队
在过去的一个半月里我第一次作为后端开发组长角色参与公司项目从0到1的开发,记录这一次开发的经历。 1、背景介绍 首先说明一下背景。我所在的公司是做智慧社区相关业务,开发的项目是系统升级工具,方便公司实施同事安装和升级系统。 参与后…...
Python文件操作(02):读文件
一、读文本文件 打开文件读文件内容关闭文件 1、在读取文件内容后进行解码操作 """ 1. 打开文件- 路径:相对路径:当前项目(读文件.py)所在的目录下查找需要读取的文件绝对路径:文件--右键--Copy Pat…...
Flink(java版)
watermark 时间语义和 watermark 注意:数据进入flink的时间:如果用这个作为时间语义就不存在问题,但是开发中往往会用处理时间 作为时间语义这里就需要考虑延时的问题。 如上图,数据从kafka中获取出来,从多个分区中获取…...
什么是动态组件以及使用场景
文章目录 一、vue中的动态组件是什么?有什么用?二、使用demo1.tab页签中的使用2.模拟新闻页demo 三、用keep-alive包裹,保持状态总结 一、vue中的动态组件是什么?有什么用? 动态组件指可以动态切换组件的显示和隐藏。…...
CRM销售管理系统如何提高销售效率
CRM销售管理系统是帮助企业对销售活动进行管理、执行和优化的软件系统。它可以帮助企业提高销售效率,提高客户转化率,实现企业的业绩增长。那么,CRM销售管理系统好用吗? CRM销售管理系统的功能 线索管理: CRM系统可…...
纯小白安卓刷机1
文章目录 常见的英文意思刷机是什么?为什么要刷机?什么是BL锁(BootLoader锁)?我的机能够刷机吗?什么是Boot镜像/分区?什么是Recovery镜像/分区(缩写为rec)?什…...
C高级day4循环语句
1,思维导图 运行结果为: 运行结果为:...
Linux 操作系统云服务器安装部署 Tomcat 服务器详细教程
Tomcat 基本概述 Tomcat 服务器是Apache软件基金会(Apache Software Foundation)的 Jakarta 项目中的一个核心项目,由 Apache、Sun 和其他一些公司及个人共同开发而成。它是一个免费的开放源代码的 Web 应用服务器,属于轻量级应用…...
【易盾点选】
拿官网的点选做个例子吧,比较省事,水一篇~ 官网的接口目前都改成V3了,多了个dt参数,以及加密的一个函数也变动了下 点选坐标在这,加密函数未变,用逗号拼接 整个加密里的函数变了,直接重新…...
vue中打印指定dom元素
和window.print()效果一样,调出打印窗口,只是当前使用的插件是vue-print-nb 官网地址:vue-print-nb vue2中使用 安装插件 npm install vue-print-nb --save导入插件 import Print from vue-print-nb // 全局使用 Vue.use(Print);//or// 单…...
OpenCV(三十六):霍夫直线检测
1.检测直线的霍夫变换原理 2.检测直线函数HoughLines() 检测直线流程: Step1:将参数空间的坐标轴离散化。 Step2:将图像中每个非0像素通过映射关系求取在参数空间通过的方格 Step3:统计参数空间内每个方格出现的次数,选取次数大于某一值的方格作为表示直线的方格…...
文心一言 VS 讯飞星火 VS chatgpt (91)-- 算法导论8.3 4题
四、用go语言,说明如何在 O(n) 时间内,对 0 到 n 3 − 1 n^3-1 n3−1 区间内的n个整数进行排序。 文心一言: 在 O(n) 时间内对 0 到 n^3-1 区间内的 n 个整数进行排序,可以使用基数排序(Radix Sort)算法…...
keep-alive缓存三级及三级以上路由
需求需要缓存这个出入记录,当tab切换时不重新加载,当刷新页面时,或把这个关闭在重新打开时重新加载如图: (我这里用的是芋道源码的前端框架) keep-alive 1、include 包含页面组件name的这些组件页面,会被…...
vite vue项目 运行时 \esbuild\esbuild.exe 缺失 错误码 errno: -4058, code: ‘ENOENT‘,
vite vue项目运行 npm run dev 报错某个模块启动文件丢失信息 D:\PengYe_code\2\vite-vue3-admin>npm run dev> vite-vue3-admin1.0.2 dev > vitenode:events:504throw er; // Unhandled error event^Error: spawn D:\PengYe_code\2\vite-vue3-admin\node_modules\vi…...
favicon.ico网站图标不显示问题 Failed to load resource: net::ERR_FILE_NOT_FOU
上述问题主要由于网站的小图标无法显示导致的:可以检查如下部分: 1、是否存在一个favicon.ico文件在根目录下 2、如果存在,看是否写的相对路径:改为绝对路径 <link rel"shortcut icon" href"../favicon.ico&quo…...
微服务·架构组件之服务注册与发现-Nacos
微服务组件架构之服务注册与发现之Nacos Nacos服务注册与发现流程 服务注册:Nacos 客户端会通过发送REST请求的方式向Nacos Server注册自己的服务,提供自身的元数据,比如ip地址、端口等信息。 Nacos Server接收到注册请求后,就会…...
Linux驱动【day2】
mychrdev.c: #include <linux/init.h> #include <linux/module.h> #include <linux/fs.h> #include<linux/uaccess.h> #include<linux/io.h> #include"head.h" unsigned int major; // 保存主设备号 char kbuf[128]{0}; unsigned int…...
4、Nginx 配置实例-反向代理
文章目录 4、nginx 配置实例-反向代理4.1 反向代理实例一4.1.1 实验代码 4.3 反向代理实例二4.3.1 实验代码 【尚硅谷】尚硅谷Nginx教程由浅入深 志不强者智不达;言不信者行不果。 4、nginx 配置实例-反向代理 4.1 反向代理实例一 实现效果:使用 nginx…...
2023年世界机器人大会回顾
1、前记: 本次记录是我自己去世界机器人博览会参观的一些感受,所有回顾为个人感兴趣部分的机器人产品分享。整个参观下来最大的感受就是科学技术、特别是机器人技术和人工智能毫无疑问地、广泛的应用在我们日常生活的方方面面,在安全巡检、特…...
Mac系统 AndroidStudio Missing essential plugin:org.jetbrains.android报错
打开Android Studio,提示 Missing essential plugin:org.jetbrains.android错误,产生的原因是Kotlin被禁用。 解决的方法是删除disabled_plugins.txt,Mac OS对应的路径为: /Users/xzh/Library/Application Support/Google/AndroidStudio202…...
读书笔记:多Transformer的双向编码器表示法(Bert)-1
多Transformer的双向编码器表示法 Bidirectional Encoder Representations from Transformers,即Bert; 本笔记主要是对谷歌Bert架构的入门学习: 介绍Transformer架构,理解编码器和解码器的工作原理;掌握Bert模型架构…...
第二证券:股利支付率和留存收益率的关系?
股利付出率和留存收益率是股票出资中非常重要的目标,它们可以反映公司的盈余才能和未来开展的潜力。那么,二者之间究竟有什么联系呢? 一、股利付出率和留存收益率的定义 股利付出率是指公司向股东分配的股息占当期净利润的比例,通…...
煤矿虚拟仿真 | 采煤工人VR虚拟现实培训系统
随着科技的发展,虚拟现实(VR)技术已经逐渐渗透到各个行业,其中包括煤矿行业。VR技术可以为煤矿工人提供一个安全、真实的环境,让他们在虚拟环境中进行实际操作和培训,从而提高他们的技能水平和安全意识。 由广州华锐互动开发的采煤…...
buuctf crypto 【[GXYCTF2019]CheckIn】解题记录
1.打开文件,发现密文 2.一眼base64,解密一下 3.解密后的字符串没有什么规律,看了看大佬的wp,是rot47加密,解密一下(ROT5、ROT13、ROT18、ROT47位移编码)...
微服务05-Docker基本操作
Docker的定义 1.什么是Docker Docker是一个快速交付应用、运行应用的技术: 可以将程序及其依赖、运行环境一起打包为一个镜像,可以迁移到任意Linux操作系统运行时利用沙箱机制形成隔离容器,各个应用互不干扰启动、移除都可以通过一行命令完…...
做3D打印样品用什么外贸网站好/推广怎么推
VMware安装VMware tool是 遇到The path “” is not a valid path to the 3.10.0-693.el7.x86_64 kernel headers. The path “” is not a valid path to the 3.10.0-693.el7.x86_64 kernel headers.问题是找不到内核头文件,需要安装头文件,按照网上的方…...
怎么建网站不用买空间/今日热搜榜
概述 通道提供I/O服务的直接连接,用于缓冲区与文件或者Socket之间传输数据。JAVA中只定义了一个接口来完成对通道的抽象,在这个接口中只定义了关闭与是否打开两个方法。在此接口的基础上又分别抽象了可读通道、可写通道、可中断通道、字节通道等…...
合肥网络推广服务/企业网站优化哪家好
在jquery中最常使用的就是$这个符号了,在我没有系统的学习jquery之前,我用到的$都是用于对元素的选择,而这只是$的很简单的用法。在jquery$()函数一共有三种用法: $(selector,context)在这个方法中selector是选择器,co…...
重庆建企业网站/上海比较大的优化公司
关于如何获取webrtc的源码,请参考Webrtc代码下载这篇文章。 构建android编译环境 $ cd src/ $ source ./build/android/envsetup.sh $ export JAVA_HOME/usr/bin/ $ export GYP_DEFINES"$GYP_DEFINES OSandroid" $ export GYP_GENERATORSninja 下载编译所…...
做的比较好的货运网站/app开发流程
增强for循环实现数组遍历代码: package cn.tedu.demo; public class Demo { //增强for循环实现数组遍历 public static void main(String[] args) { int[] ages new int[]{1,4,2,45,0}; for(int a : ages){ System.out.print("–>"a); } } } 输出&…...
网站怎么做图片按按钮跳转/百度搜索引擎提交入口
晚上的时候PC问了一下这玩意,回忆一下极角排序 相关链接: How Many Triangles HDU - 5784(极角排序,双指针) 2019秦皇岛A - Angle Beats Gym - 102361A(极角排序,多少个直角三角形)…...