当前位置: 首页 > news >正文

在做题中学习(56):二维前缀和模板

【模板】二维前缀和_牛客题霸_牛客网 (nowcoder.com)

理解题意:

要求的是(x1,y1) - (x2,y2)这段区间的和。

解法:二维前缀和

1. 和一维前缀和一样,需要有一个同等规模的dp数组,用来保存一段连续区域的和。

在二维dp中,可以把数组分为四部分,如下图:

dp[xi][yi] 求的是由(1,1) - (xi,yi)区域的和,就是算A+B+C+D的和。而在此中,直接求B,C的值可不好求,因为在之前的dp数组中找不到(这就与一维数组的dp不同了),所以结合一下,先求A+B,A+C的和,再减去多加的A即可。

2.使用前缀和dp

要求的是中间一段区间的面积:D

int main() 
{//1.把值输入到原始数组int n = 0,m = 0,q = 0;cin >> n >> m >> q;vector<vector<int>> arr(n+1,vector<int>(m+1));for(int i = 1;i<=n;i++)for(int j = 1;j<=m;j++)cin >> arr[i][j];//2.创建dp数组vector<vector<long long int>> dp(n+1,vector<long long int>(m+1));for(int i = 1;i<=n;i++)for(int j = 1;j<=m;j++)dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1];//3.使用dp数组int x1 = 0,y1 = 0,x2 = 0,y2 = 0;while(q--){cin >> x1 >> y1 >> x2 >> y2;cout<< dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] <<endl;}
}

相关文章:

在做题中学习(56):二维前缀和模板

【模板】二维前缀和_牛客题霸_牛客网 (nowcoder.com) 理解题意&#xff1a; 要求的是(x1,y1) - (x2,y2)这段区间的和。 解法&#xff1a;二维前缀和 1. 和一维前缀和一样&#xff0c;需要有一个同等规模的dp数组&#xff0c;用来保存一段连续区域的和。 在二维dp中&#xff0…...

驾驭多云环境,加速AI创新丨Animbus Cloud 8.3.0 算力调度平台升级发布

大模型开启全球新一轮AI浪潮&#xff0c;伴随算力规模的爆发增长以及计算技术的多元创新&#xff0c;需要更稳定、高效、敏捷的异构计算基础设施&#xff0c;才能充分发挥对算力能力的重要支撑。 作为开放智能云边架构引领者&#xff0c;九州未来凭借多年的技术积累、实践沉淀…...

JavaScript异步编程——02-Ajax入门和发送http请求

同步和异步回顾 同步和异步的简单理解 同步&#xff1a;必须等待前面的任务完成&#xff0c;才能继续后面的任务。 异步&#xff1a;不受当前任务的影响。 拿排队举例&#xff1a; 同步&#xff1a;在银行排队时&#xff0c;只有等到你了&#xff0c;才能够去处理业务。 异…...

湖仓一体 - Apache Arrow的那些事

湖仓一体 - Apache Arrow的那些事 Arrow是高性能列式内存格式标准。它的优势&#xff1a;高效计算&#xff1a;所有列存的通用优势&#xff0c;CPU缓存友好、SIMD向量化计算友好等&#xff1b;零序列化/反序列化&#xff1a;arrow的任何数据结构都是一段连续的内存&#xff0c;…...

常用的启发式算法:探索问题解决的智慧之道

启发式算法是一种通过启发式信息来引导搜索的算法&#xff0c;常用于解决那些在合理时间内难以找到最优解的问题。本文将介绍几种常用的启发式算法&#xff0c;包括贪心算法、遗传算法和模拟退火算法&#xff0c;并提供Java代码实现及测试&#xff0c;帮助读者深入理解这些算法…...

docker Harbor私有仓库部署管理

搭建本地私有仓库&#xff0c;但是本地私有仓库的管理和使用比较麻烦&#xff0c;这个原生的私有仓库并不好用&#xff0c;所以我们采用harbor私有仓库&#xff0c;也叫私服&#xff0c;更加人性化。 一、什么是Harbor Harbor是VWware 公司开源的企业级Docker Registry项…...

序列化的不同格式:JSON、XML、TOML、CSON、YAML

前言 这篇文章参考于知乎&#xff0c;进行了一些总结。 正文 首先什么是序列化&#xff0c;数据序列化是从一个系统获取一些信息&#xff0c;将其转换为其它系统可以读取的格式&#xff0c;然后将其传递给其它系统的过程。也就是可以让不同系统“通信”。 序列化需要满足两…...

Mapreduce | 案例

根据提供的数据文件【test.log】 数据文件格式&#xff1a;姓名,语文成绩,数学成绩,英语成绩 完成如下2个案例&#xff1a; &#xff08;1&#xff09;求每个学科的平均成绩 &#xff08;2&#xff09;将三门课程中任意一门不及格的学生过滤出来 &#xff08;1&#xff09;求每…...

U盘文件剪切丢失怎么办?揭秘原因并给出恢复方法

在日常生活和工作中&#xff0c;U盘已成为我们不可或缺的数据存储和传输工具。但有时候&#xff0c;我们在对U盘中的文件进行剪切操作时&#xff0c;会遇到文件丢失的情况。这种突如其来的数据消失往往会让人感到惊慌和困惑。那么&#xff0c;为什么U盘剪切时文件会丢失呢&…...

软件设计师考试---访问控制列表、堆,栈和堆栈、防火墙、数据流图、嵌入式操作、绑定方式、uml、模式、传输协议

访问控制列表 访问控制列表&#xff08;Access Control List&#xff0c;ACL&#xff09; 是一种用于控制对资源&#xff08;如文件、目录、网络资源等&#xff09;访问权限的方法。ACL是在计算机安全领域广泛使用的概念&#xff0c;它允许系统管理员定义哪些用户或系统进程有…...

vlock工具:锁定Linux终端的安全智能方法

虚拟控制台是 Linux 非常重要的功能&#xff0c;它们为系统用户提供 shell 提示&#xff0c;以非图形设置方式使用系统&#xff0c;该设置只能在物理机上使用&#xff0c;而不能远程使用。 用户只需从一个虚拟控制台切换到另一个虚拟控制台即可同时使用多个虚拟控制台会话。 …...

【Linux】Docker 安装部署 Nacos

个人简介&#xff1a;Java领域新星创作者&#xff1b;阿里云技术博主、星级博主、专家博主&#xff1b;正在Java学习的路上摸爬滚打&#xff0c;记录学习的过程~ 个人主页&#xff1a;.29.的博客 学习社区&#xff1a;进去逛一逛~ 【Linux】Docker 安装部署 Nacos docker搜索na…...

纯血鸿蒙APP实战开发——阅读翻页方式案例

介绍 本示例展示手机阅读时左右翻页&#xff0c;上下翻页&#xff0c;覆盖翻页的功能。 效果图预览 使用说明 进入模块即是左右翻页模式。点击屏幕中间区域弹出上下菜单。点击设置按钮&#xff0c;弹出翻页方式切换按钮&#xff0c;点击可切换翻页方式。左右翻页方式可点击翻…...

如何从Mac电脑恢复任何删除的视频

Microsoft Office是包括Mac用户在内的人们在世界各地创建文档时使用的最佳软件之一。该软件允许您创建任何类型的文件&#xff0c;如演示文稿、帐户文件和书面文件。您可以使用 MS Office 来完成。所有Microsoft文档都可以在Mac上使用。大多数情况下&#xff0c;您处理文档&…...

【Halcon 内存泄漏记录 - C#】

Halcon 内存泄漏记录 - C# 1. Bitmap 转 HImage2. new 之后要Dispose()3. 切换配方后&#xff0c;内存会增加4. Parallel.For 嵌套Parallel.For&#xff0c; 会出现问题5. 图像预处理使用需要注意不能直接在原有变量上赋值 1. Bitmap 转 HImage 由于Bitmap 在转化时使用Bitmap…...

MT8370_联发科MTK8370(Genio 510)芯片性能规格参数

MT8370芯片是一款利用超高效的6nm制程工艺打造的边缘AI平台&#xff0c;具有强大的性能和功能。这款芯片集成了六核CPU(2x2.2 GHz Arm Cortex-A78 & 4x2.0 GHz Arm Cortex-A55)、Arm Mali-G57 MC2 GPU、集成的APU(AI处理器)和DSP&#xff0c;以及一个HEVC编码加速引擎&…...

【Qt 学习笔记】Qt常用控件 | 多元素控件 | Table Widget的说明及介绍

博客主页&#xff1a;Duck Bro 博客主页系列专栏&#xff1a;Qt 专栏关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ Qt常用控件 | 多元素控件 | Table Widget的说明及介绍 文章编号&#…...

ES全文检索支持拼音和繁简检索

ES全文检索支持拼音和繁简检索 1. 实现目标2. 引入pinyin插件2.1 编译 elasticsearch-analysis-pinyin 插件2.2 安装拼音插件 3. 引入ik分词器插件3.1 已有作者编译后的包文件3.2 只有源代码的版本3.3 安装ik分词插件 4. 建立es索引5.测试检索6. 繁简转换 1. 实现目标 ES检索时…...

【DDR 终端稳压器】Sink and Source DDR Termination Regulator [C] S0 S1 S2 S3 S4 S5 6状态

TPS51200A-Q1 器件通过 EN 功能提供 S3 支持。EN引脚可以连接到终端应用中的SLP_S3信号。当EN 高电平&#xff08;S0 状态&#xff09;时&#xff0c;REFOUT 和 VO 引脚均导通。当EN 低电平&#xff08;S3状态&#xff09;时&#xff0c;VO引脚关断并通过内部放电MOSFET放电时…...

使用IIS部署Vue项目

前提 使用IIS部署Vue项目&#xff0c;后端必须跨域&#xff0c;不要在Vue中用proxy跨域&#xff0c;那个只在dev环境中有用&#xff01; IIS安装&#xff0c;不用全部打勾&#xff0c;有些他默认就是方块 ■ 选择性安装的&#xff0c;就维持原样就可以。 添加网站配置 右键…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

Python第七周作业

Python第七周作业 文章目录 Python第七周作业 1.使用open以只读模式打开文件data.txt&#xff0c;并逐行打印内容 2.使用pathlib模块获取当前脚本的绝对路径&#xff0c;并创建logs目录&#xff08;若不存在&#xff09; 3.递归遍历目录data&#xff0c;输出所有.csv文件的路径…...

python学习day39

图像数据与显存 知识点回顾 1.图像数据的格式&#xff1a;灰度和彩色数据 2.模型的定义 3.显存占用的4种地方 a.模型参数梯度参数 b.优化器参数 c.数据批量所占显存 d.神经元输出中间状态 4.batchisize和训练的关系 import torch import torchvision import torch.nn as nn imp…...