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 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...
uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)
UniApp 集成腾讯云 IM 富媒体消息全攻略(地理位置/文件) 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型,核心实现方式: 标准消息类型:直接使用 SDK 内置类型(文件、图片等)自…...
DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...
机器学习的数学基础:线性模型
线性模型 线性模型的基本形式为: f ( x ) ω T x b f\left(\boldsymbol{x}\right)\boldsymbol{\omega}^\text{T}\boldsymbol{x}b f(x)ωTxb 回归问题 利用最小二乘法,得到 ω \boldsymbol{\omega} ω和 b b b的参数估计$ \boldsymbol{\hat{\omega}}…...
解析“道作为序位生成器”的核心原理
解析“道作为序位生成器”的核心原理 以下完整展开道函数的零点调控机制,重点解析"道作为序位生成器"的核心原理与实现框架: 一、道函数的零点调控机制 1. 道作为序位生成器 道在认知坐标系$(x_{\text{物}}, y_{\text{意}}, z_{\text{文}}…...
【51单片机】4. 模块化编程与LCD1602Debug
1. 什么是模块化编程 传统编程会将所有函数放在main.c中,如果使用的模块多,一个文件内会有很多代码,不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里,在.h文件里提供外部可调用函数声明,其他.c文…...
