[题] 差分矩阵 #差分
题目
差分矩阵
题解
只有一个操作:
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;
}
利用差分的思想,扩展到二维上。
insert函数作用是将矩阵之内的数全部加上c, 其余部分不会变。
而最后的实现其实就是前面子矩阵的和这道题的方法,也就是将最后得到的b数组进行二维前缀和的操作,
得到的b数组就是答案
举例理解:
首先 假设 有一个4X4 的小方块要加上 2, 那么我们先将方块的左上角(1, 1)加上2。然后你想,我们最后是要进行二维前缀和的运算的,那么为了不让其它部分受到影响,我们要将(1, 5)(5, 1)上的数减去2,抵消从(1, 1)传递过来的2的影响,这样后面的数也不会受到影响了。注意!有一个位置,就是b(5, 5)它减去了两次2!因为它同时受b(5, 1)b(1, 5)的影响,所以我们还要在b(5, 5)再加上2.
代码
答案
#include <bits/stdc++.h>
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(){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]);}for(int i = 1; i <= q; i ++){int x1, x2, y1, 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];for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++)printf("%d ", b[i][j]);puts("");} return 0;
}
相关文章:
[题] 差分矩阵 #差分
题目 差分矩阵 题解 只有一个操作: 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; }利用差分的思想,扩展到二维上。 insert函数作用是将矩阵之内的数全部加上c,…...
Studio One6.5最新版本新增了对Linux的支持
音乐制作人们,这是你们翘首以待的消息。数字音频工作站(DAW)已经成为音乐制作专业人士重要工具之一。 遗憾的是,对于 Linux 用户而言,选择十分有限。最受欢迎的选择通常是开源 DAW,如 Ardour、Audacity和闭…...
大模型引发“暴力计算”,巨头加速推进液冷“降温”
点击关注 文|姚悦 编|王一粟 一进入部署了液冷服务器的数据中心,不仅没有嘈杂的风扇声,甚至在不开空调的夏日也完全没有闷热感。 在大模型引发“暴力计算”的热潮下,数据中心的上下游,正在加紧推进液冷“…...
git log 美化配置
编辑 vim ~/.gitconfig 添加配置 [alias]lg log --graph --abbrev-commit --decorate --dateformat:%m-%d %H:%M:%S --formatformat:%C(bold blue)%h%C(reset) - %s %C(bold yellow)% d%C(reset) %n %C(dim white) (%ad) - %an%C(reset) --allgit lg 效果...
Spark 的主要组件及任务分工
Spark 是一个开源的分布式计算框架,旨在处理大规模数据集的快速计算和分析。下面是 Spark 的主要组件及其任务分工的详细介绍: Driver(驱动器):【任务调度】 负责整个 Spark 应用程序的执行和协调。解析用户程序&#…...
Apache Spark 中的 RDD是什么
目录 RDD容错性 RDD进行迭代计算 RDD是Resilient Distributed Dataset的缩写,是Apache Spark中的一个关键概念。RDD是一种分布式的内存抽象,用于将数据划分为不同的片段以进行并行计算。RDD是一个只读的数据集,可以分布在集群的不同节点上&…...
idea自动封装方法
例如 package com.utils;import java.lang.reflect.Field; import java.sql.*; import java.util.ArrayList; import java.util.List; import java.util.ResourceBundle;/*** author hrui* date 2023/10/13 13:49*/ public class DBUtils {private static ResourceBundle bund…...
js正则表达式
1.字符类 \w 匹配字母数字下划线,相当于[0-9A-Za-z_] \s 匹配单个空白字符,包括空格、制表符、回车符、换行符 \b 匹配一个词的边界 2.边界符 如果不加任何边界符,则表示包含。以下只要包含即可 // /123/ 匹配内容是否包含有123var rg …...
服务安全-应用协议rsync未授权ssh漏洞复现
目录 服务攻防-应用协议rsync&ssh漏洞复现漏洞复现配置不当-未授权访问-rsync文件备份OpenSSH 用户名枚举漏洞libssh身份验证绕过漏洞 服务攻防-应用协议rsync&ssh漏洞复现 漏洞复现 配置不当-未授权访问-rsync文件备份 rsync默认端口:873 rsync是Linux下…...
[环境搭建]OpenHarmony开发环境搭建
文章目录 1. 开发工具1.1 虚拟机1.2 Ubuntu镜像 2 虚拟机安装和配置2.1 虚拟机安装2.2 生成SSH KEY2.3 配置国内apt源&更新2.4 sh修改为bash2.5 下载OpenHarmony依赖工具2.6 python软链接2.7 samba配置 3. gitee账号注册4. 配置git和Repo4.1 git配置4.2 Repo 1. 开发工具 …...
[牛客习题]“幸运的袋子”
习题链接:幸运的袋子_牛客题霸_牛客网 题目分析 由题意可知:“幸运的袋子”的概念是——小球的数值之和大于小球的数值之积。 假如现在有5个小球:1,1,3,5,7,并将他们编号a0~a4.我们…...
安科瑞预付费系统在某大型连锁农贸市场的设计应用
安科瑞 崔丽洁 摘要 本远程预付费管理系统采用智能远程预付费电表(DTSY1352-NK/DDSY1352-NK系列),NB智能远传水表,采集各商户实时用电量、用电量总数,通过平台定时结算,结算账户余额,从而进行智…...
Spring Boot Bean 注入的常用方式教程
Spring Boot Bean 注入是一种将依赖对象引入到应用程序组件中的机制,它有助于实现松耦合和可测试的代码。这种注入方式允许我们将依赖关系委托给 Spring 容器来管理,从而提高了代码的可维护性和可读性。Spring Boot 提供了多种 Bean 注入方式,…...
Java项目调用Python脚本(基于idea)
前期准备 1.首先需要在本地环境中安装配置python环境 Python(含PyCharm及配置)下载安装以及简单使用(Idea) 博主本次使用python版本为py3.7.3 2.idea安装python插件 位置:File->Settings->Plugins->python->安装后重启即可 3.引入jython依赖 &l…...
前端 JS 经典:i,i++,++i区别
1. 概念 用于对变量进行自增操作。它们的区别在于返回值不同。 i 表示先使用 i 的值,再将 i 加 1,返回的是 i 自增前的值。 i 表示先将 i 加 1,再使用 i 的值,返回的是 i 自增后的值。 i 表示直接使用 i 的值,不进…...
EF Core 7.0 新特性之批量修改
概要 EF Core 7.0 提供了一个可以将LINQ查询和批量修改相结合的方法ExecuteUpdate。由于数据修改是以批量更新的方式完成,所以可以减少数据库的往返次数。 本文将主要介绍ExecuteUpdate的使用方法。 代码和实现 基本案例 本文我们使用银行分行,ATM机…...
Vue_Bug error0308010Cdigital envelope routinesunsupported
Bug描述: error0308010Cdigital envelope routinesunsupported 解决方法: Just add this to the top of vue.config.js : const crypto require(crypto);/*** md4 algorithm is not available anymore in NodeJS 17 (because of lib SSL 3).* In that…...
中科院提出“思维传播”,极大增强ChatGPT等模型复杂推理能力
中国科学院自动化研究所与耶鲁大学计算机系研究人员联合发布了,一份名为《思维传播:用大型语言模型进行基于类比的复杂推理》的论文。 ChatGPT等大型语言模型展示出了超强的创造能力,只需简单的文本提示就能生成小说、营销创意、简历等各种文本内容。但…...
ubuntu20.04安装opencv 3.2.0 报错
安装记录 Error 1: cmake时报错 CMake Error at cmake/OpenCVCompilerOptions.cmake:21 (else): A duplicate ELSE command was found inside an IF block. Fix: 修改opencv-3.2.0/cmake/OpenCVCompilerOptions.cmake文件 注释掉21和22行 else()message(STATUS "Unabl…...
KubeVela交付
有什么用我也不想说了,这个是k8s CI/CD,进阶玩家玩的了,比你们喜欢Arg CD更科学,更现代 在 Kubernetes 中安装 KubeVela helm repo add kubevela https://charts.kubevela.net/core helm repo update helm install --create-namespace -n v…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
