AcWing 798. 差分矩阵
题目来源:
找不到页面 - AcWing
题目内容:
输入一个 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 n,m,q;
int a[N][N],b[N][N];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(){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 ++ )insert(i, j, i, j, a[i][j]);while(q--){int x1,y1,x2,y2,c;cin>>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];} } for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<b[i][j]<<" "; }cout<<endl;}return 0;
}
题目心得:
- 二维差分结论:
给以(x1,y1)为左上角,(x2,y2)为右下角的子矩阵中的所有元素加上c:void insert(int x1,int y1,int x2,int y2,int c) { //对b数组执行插入操作,等价于对a数组中的(x1,y1)到(x2,y2)之间的元素都加上了cb[x1][y1]+=c;b[x2+1][y1]-=c;b[x1][y2+1]-=c;b[x2+1][y2+1]+=c; }
相关文章:
AcWing 798. 差分矩阵
题目来源: 找不到页面 - AcWing 题目内容: 输入一个 n 行 m 列的整数矩阵,再输入 q 个操作,每个操作包含五个整数 x1,y1,x2,y2,c,其中 (x1,y1) 和 (x2,y2)表示一个子矩阵的左上角坐标和右下角坐标。 每个操作都要将…...
通用定时器学习记录
简介 通用定时器:TIM2/TIM3/TIM4/TIM5 主要特性:16位递增、递减、中心对齐计数器(计数值0~65535) 16位预分频器(分频系数1~65536) 可用于触发DAC、ADC 在更新事件、触发事件、输入捕获、输出比较时&am…...
科技之光闪耀江城:2025武汉国际半导体产业与电子技术博览会5月15日盛大开幕
在科技浪潮汹涌澎湃的当下,半导体产业作为现代信息技术的中流砥柱,正以令人惊叹的速度重塑着世界的面貌。2025年5月15-17日,一场聚焦半导体与电子技术前沿的行业盛会 ——2025 武汉国际半导体产业与电子技术博览会,将在武汉・中国…...
vue开发06:前端通过webpack配置代理处理跨域问题
1.定义 在浏览器尝试请求不同源(域名、协议、端口号不同)的资源时,浏览器的同源策略会阻止这种跨域请求。(比如前端端口15500,后端端口5050,前端界面不可以直接调用5050端口) 2.解决方案 使用前…...
⚡️《静电刺客的猎杀手册:芯片世界里的“千伏惊魂“》⚡️
前言: 在这个电子产品无孔不入的时代,我们每天都在与一群隐形刺客打交道——它们身怀数千伏特的高压绝技,能在0.1秒内让价值百万的芯片灰飞烟灭。这就是静电放电(ESD),电子工业界最令人闻风丧胆的"沉默…...
【云安全】云原生-K8S(三) 安装 Dashboard 面板
在Kubernetes中安装Dashboard需要几个步骤,包括部署Dashboard组件、配置访问权限以及暴露Dashboard服务等。以下是详细的步骤: 1. 部署 K8S Dashboard 可以通过以下命令用Kubernetes官方的YAML文件来快速部署,由于是国外网站,需…...
Spring Boot 常用依赖详解:如何选择和使用常用依赖
在Spring Boot项目中,依赖(Dependencies)是项目的核心组成部分。每个依赖都提供了一些特定的功能或工具,帮助我们快速开发应用程序。本文将详细介绍Spring Boot中常用的依赖及其作用,并指导你如何根据项目需求选择合适…...
C++ 设计模式-组合模式
组合模式(Composite Pattern)允许将对象组合成树形结构,使得客户端以统一的方式处理单个对象和组合对象。以下是一个经典的 C 实现示例,包含透明式设计(基类定义统一接口)和内存管理: #include…...
【Spring Boot】Spring 魔法世界:Bean 作用域与生命周期的奇妙之旅
前言 ???本期讲解关于spring原理Bean的相关知识介绍~~~ ??感兴趣的小伙伴看一看小编主页:-CSDN博客 ?? 你的点赞就是小编不断更新的最大动力 ??那么废话不多说直接开整吧~~ 目录 ???1.Bean的作用域 ??1.1概念 ??1.2Bean的作用域 ??1.3代码演示…...
移远通信边缘计算模组成功运行DeepSeek模型,以领先的工程能力加速端侧AI落地
近日,国产大模型DeepSeek凭借其“开源开放、高效推理、端侧友好”的核心优势,迅速风靡全球。移远通信基于边缘计算模组SG885G,已成功实现DeepSeek模型的稳定运行,并完成了针对性微调。 目前,该模型正在多款智能终端上进…...
Cables Finance 构建集成LST与外汇RWA永续合约的综合性DEX
虽然 DeFi 领域整体发展迅速,但仍旧缺乏交易体验。现阶段市场已拓展至 RWAs 、永续期货和外汇领域,但跨资产交易的实际操作仍充满阻力。交易者面临流动性碎片化、抵押品被锁定在质押合约中缺乏流动性,以及整个系统仍围绕美元稳定币运转等问题…...
AI大模型(DeepSeek)科研应用、论文写作、数据分析与AI绘图学习
【介绍】 在人工智能浪潮中,2024年12月中国公司研发的 DeepSeek 横空出世以惊艳全球的姿态,成为 AI领域不可忽视的力量!DeepSeek 完全开源,可本地部署,无使用限制,保护用户隐私。其次,其性能强大ÿ…...
【算法工程】解决linux下Aspose.slides提示No usable version of libssl found以及强化推理模型的短板
1. 背景 构建ubuntu镜像,然后使用Aspose.slides解析PPTX文档,发现一直提示“No usable version of libssl found”。 2. 尝试 使用deepseek R1、kimi1.5、chatgpt o3,并且都带上联网能力,居然还是没有一个能够真正解决…...
什么是HTTP和HTTPS?它们之间有什么区别?
什么是HTTP和HTTPS?它们之间有什么区别? HTTP(超文本传输协议)简介 HTTP就像是你通过明信片给朋友发送信息。你在明信片上写下内容,然后寄出去。任何人都可以在途中看到明信片上的内容,因为它是公开的。 …...
【一文读懂】TCP与UDP协议
TCP协议 概述 TCP(Transmission Control Protocol),即传输控制协议,是一种面向连接的、可靠的、基于字节流的传输层通信协议,常用于保证数据可靠、按顺序、无差错地传输。TCP 是互联网协议族(TCP/IP&…...
数据结构 树的存储和遍历
一、树的定义 树的定义 树型结构是⼀类重要的⾮线性数据结构。 • 有⼀个特殊的结点,称为根结点,根结点没有前驱结点。 • 除根结点外,其余结点被分成M个互不相交的集合T1 、T2 、...、Tm T,其中每⼀个集合⼜是⼀棵树,…...
Jenkins项目CICD流程
Jenkins项目流程:1.配置git环境 git config --...2.把前后端的目录初始化位本地工作目录 #git init3.提交到本地git #git add ./ git commit -m "" git tag v14.然后提交到远程git(通过,用户,群组,项目,管理项目)git remote add origin http://...git push -…...
EasyRTC轻量级SDK:智能硬件音视频通信资源的高效利用方案
在智能硬件这片广袤天地里,每一份资源的精打细算都关乎产品的生死存亡。随着物联网技术的疾速演进,实时音视频通信功能已成为众多设备的标配。然而,硬件资源的捉襟见肘,让开发者们常常陷入两难境地。EasyRTC,以它的极致…...
AI Agent未来走向何方?
AI Agent未来走向何方? 目录 AI Agent未来走向何方?AI推理支撑应用开发走向新赛道智能体成为AI应用的主流形式大模型应用正以AI Agent的主流形式赋能终端设备从大到小AI模型发展从通用转向垂直:小型语言模型(SLM)AI推理支撑应用开发走向新赛道 训练与推理,是AI 大模型两大核…...
Visual Studio Code的键盘快捷键
注意:如果您在Mac上访问此页面,您将看到Mac的键盘快捷键。如果您使用Windows或Linux访问,您将看到该平台的密钥。如果您需要其他平台的键盘快捷键,请将鼠标悬停在您感兴趣的键上。 键盘快捷键编辑器 VS Code通过键盘快捷键编辑器…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
【LeetCode】算法详解#6 ---除自身以外数组的乘积
1.题目介绍 给定一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O…...
Oracle11g安装包
Oracle 11g安装包 适用于windows系统,64位 下载路径 oracle 11g 安装包...
