当前位置: 首页 > 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;就维持原样就可以。 添加网站配置 右键…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...