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

刷题——【模板】二维前缀和

前缀和

  • 题目
    • 题目链接
    • 题解
      • 方法一
      • 方法二

题目

描述
给你一个 n 行 m 列的矩阵 A ,下标从1开始。

接下来有 q 次查询,每次查询输入 4 个参数 x1 , y1 , x2 , y2

请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和,
输入描述:
第一行包含三个整数n,m,q.

接下来n行,每行m个整数,代表矩阵的元素

接下来q行,每行4个整数x1, y1, x2, y2,分别代表这次查询的参数
在这里插入图片描述

输出描述:
输出q行,每行表示查询结果。

在这里插入图片描述

题目链接

二维前缀和题目链接

题解

方法一

显而易见,最容易想到的方法就是先录入数据,然后一行一行的求和。但是这种方法会超时。其时间复杂度为O(m * n * q)。

#include <iostream>
#include <vector>using namespace std;int main() {int n, m, q;cin >> n >> m >> q;vector<vector<int>> matrix(n, vector<int>(m));for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> matrix[i][j];}}for (int i = 0; i < q; ++i) {int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;int sum = 0;for (int row = x1 - 1; row <= x2 - 1; ++row) { // 数组是从0开始的,所以要减1for (int col = y1 - 1; col <= y2 - 1; ++col) {sum += matrix[row][col];}}cout << sum << endl;}return 0;
}

不多赘述,下面看最优解。

方法二

一遍遍求显然复杂度太高,那么能不能先求取(1,1)到(x,y)的和在找规律求取题目要求的和呢?答案是可以的。

先求前缀和数组,显然我们不能每次都遍历一次求和,复杂度太高,那么就可以利用前面已经求出的值求出当前的和。

ps:因为下标从1开始,所以不用考虑越界。
在这里插入图片描述

由此可以得出D区域的求和公式为dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j];

再求某一个小区域的和,与此类似,画图总结公式,利用已知和求取。

在这里插入图片描述
由此可以得出D区域的求和公式为dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];

最终代码

#include <iostream>
#include <vector>
using namespace std;int main() 
{int n, m, q;cin >> n >> m >> q;vector<vector<int>> arr(n+1,vector<int>(m+1));vector<vector<long long>> dp(n+1,vector<long long>(m+1));for (int i = 1; i <= n; i++) for(int j = 1; j <= m; j++)cin >> arr[i][j];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] - dp[i-1][j-1] + arr[i][j];int x1,y1, x2, y2;long long sum = 0;for (int i = 1; i <= q; i++) {cin >> x1 >> y1 >> x2 >> y2;sum = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];cout << sum << endl;}return 0;
}

相关文章:

刷题——【模板】二维前缀和

前缀和 题目题目链接题解方法一方法二 题目 描述 给你一个 n 行 m 列的矩阵 A &#xff0c;下标从1开始。 接下来有 q 次查询&#xff0c;每次查询输入 4 个参数 x1 , y1 , x2 , y2 请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和&#xff0c; 输入描述&#x…...

Xilinx 7 系列 FPGA的各引脚外围电路接法

Xilinx 7系列FPGA的外围电路接法涉及到多个方面&#xff0c;包括电源引脚、时钟输入引脚、FPGA配置引脚、JTAG调试引脚&#xff0c;以及其他辅助引脚。 本文参考资料&#xff1a; ds180 - 7 Series FPGAs Data Sheet - Overview ds181 - Artix 7 FPGAs Data Sheet - DC and AC…...

Python 爬虫 (1)基础 | 目标网站

一、目标网站 1、加密网站 1.1、关键字比较明确 企名片&#xff1a;https://wx.qmpsee.com/articleDetail?idfeef62bfdac45a94b9cd89aed5c235be 1.2、关键字比较泛 烯牛数据&#xff1a;https://www.xiniudata.com/project/event/lib/invest...

数字后端零基础入门系列 | Innovus零基础LAB学习Day11(Function ECO流程)

###LAB 20 Engineering Change Orders (ECO) 这个章节的学习目标是学习数字IC后端实现innovus中的一种做function eco的flow。对于初学者&#xff0c;如果前面的lab还没掌握好的&#xff0c;可以直接跳过这节内容。有时间的同学&#xff0c;可以熟悉掌握下这个flow。 数字后端…...

量子卷积神经网络

量子神经网络由量子卷积层、量子池化层和量子全连接层组成 量子卷积层和量子池化层交替放置&#xff0c;分别实现特征提取和特征降维&#xff0c;之后通过量子全连接层进行特征综合 量子卷积层、量子池化层和量子全连接层分别由量子卷积单元、量子池化单元和量子全连接单元组…...

储能电站构成及控制原理

系列文章目录 能量管理系统(EMS)储能充放电策略 文章目录 系列文章目录一、储能电站构成二、储能系统关键部件及作用1.电池储能系统2.功率变换系统(Power Conversion System,PCS)3.变配电系统4.后台监控系统5.继电保护及安全自动装置 三、储能电站的功能四、储能电站控制策略 …...

Rocky Linux 系统安装/部署 Docker

1、下载docker-ce的repo文件 [rootlocalhost ~]# curl https://download.docker.com/linux/centos/docker-ce.repo -o /etc/yum.repos.d/docker.repo % Total % Received % Xferd Average Speed Time Time Time Current Dloa…...

12 —— Webpack中向前端注入环境变量

需求&#xff1a;开发模式下打印语句生效&#xff0c;生产模式下打印语句失效 使用Webpack内置的DefinePlugin插件 const webpack require(webpack) module.exports { plugins: [ new webpack.DefinePlugin({ process.env.NODE_ENV:JSON.stringify(process.env.NODE_ENV) }…...

uniapp接入BMapGL百度地图

下面代码兼容安卓APP和H5 百度地图官网&#xff1a;控制台 | 百度地图开放平台 应用类别选择《浏览器端》 /utils/map.js 需要设置你自己的key export function myBMapGL1() {return new Promise(function(resolve, reject) {if (typeof window.initMyBMapGL1 function) {r…...

外卖系统开发实战:从架构设计到代码实现

开发一套外卖系统&#xff0c;需要在架构设计、技术选型以及核心功能开发等方面下功夫。这篇文章将通过代码实例&#xff0c;展示如何构建一个基础的外卖系统&#xff0c;从需求梳理到核心模块的实现&#xff0c;帮助你快速掌握开发要点。 一、系统架构设计 一个完整的外卖系…...

神经网络反向传播算法公式推导

要推导反向传播算法&#xff0c;并了解每一层的参数梯度如何计算&#xff0c;以及每一层的梯度受到哪些值的影响&#xff0c;我们使用一个简单的神经网络结构&#xff1a; 输入层有2个节点一个有2个节点的隐藏层&#xff0c;激活函数是ReLU一个输出节点&#xff0c;激活函数是…...

Spark SQL 之 QueryStage

ExchangeQueryStageExec ExchangeQueryStageExec 分为两种...

【shodan】(三)vnc漏洞利用

shodan基础&#xff08;三&#xff09; 声明&#xff1a;该笔记为up主 泷羽的课程笔记&#xff0c;本节链接指路。 警告&#xff1a;本教程仅作学习用途&#xff0c;若有用于非法行为的&#xff0c;概不负责。 count count命令起到一个统计计数的作用。 用上节的漏洞指纹来试…...

每日OJ_牛客_游游的字母串_枚举_C++_Java

目录 牛客_游游的字母串_枚举 题目解析 C代码 Java代码 牛客_游游的字母串_枚举 游游的字母串 描述&#xff1a; 对于一个小写字母而言&#xff0c;游游可以通过一次操作把这个字母变成相邻的字母。a和b相邻&#xff0c;b和c相邻&#xff0c;以此类推。特殊的&#xff0…...

51c深度学习~合集8

我自己的原文哦~ https://blog.51cto.com/whaosoft/12491632 #patchmix 近期中南大学的几位研究者做了一项对比学习方面的工作——「Inter-Instance Similarity Modeling for Contrastive Learning」&#xff0c;主要用于解决现有对比学习方法在训练过程中忽略样本间相似关系…...

嵌入式:Flash的分类以及Jlink/J-flash的编程支持

相关阅读 嵌入式https://blog.csdn.net/weixin_45791458/category_12768532.html?spm1001.2014.3001.5482 常见的Flash大致可以分为以下大类&#xff1a; Serial Nor FlashSerial Nand FlashParallel Nor FlashParallel Nand FlashSerial EEPROM Serial Nor Flash 介绍 Se…...

【爬虫】Firecrawl对京东热卖网信息爬取(仅供学习)

项目地址 GitHub - mendableai/firecrawl: &#x1f525; Turn entire websites into LLM-ready markdown or structured data. Scrape, crawl and extract with a single API. Firecrawl更多是使用在LLM大模型知识库的构建&#xff0c;是大模型数据准备中的一环&#xff08;在…...

遗传算法(Genetic Algorithm, GA)

简介 遗传算法&#xff08;Genetic Algorithm, GA&#xff09;是一种基于自然选择和遗传机制的优化算法&#xff0c;由 John Holland 于20世纪70年代提出。它是一种模拟生物进化过程的启发式搜索算法&#xff0c;被广泛应用于函数优化、机器学习、调度问题等领域。 代码说明 …...

【二分答案+倍增快速幂】课堂练习

P1678 烦恼的高考志愿 #include<bits/stdc.h> using namespace std; const int N1e55; int n,m,a[N];long long bs(int x){int l1,rn;while(l<r){int midlr>>1;if(a[mid]x) return 0;if(a[mid]>x) rmid-1;else lmid1;}//根据前驱后继返回最小差值//printf(&…...

LeetCode 力扣 热题 100道(九)反转链表(C++)

给你单链表的头节点 head &#xff0c;请你反转链表&#xff0c;并返回反转后的链表。 方法一&#xff1a;迭代法 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNod…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础

第三周 Day 3 &#x1f3af; 今日目标 理解类&#xff08;class&#xff09;和对象&#xff08;object&#xff09;的关系学会定义类的属性、方法和构造函数&#xff08;init&#xff09;掌握对象的创建与使用初识封装、继承和多态的基本概念&#xff08;预告&#xff09; &a…...

ZYNQ学习记录FPGA(一)ZYNQ简介

一、知识准备 1.一些术语,缩写和概念&#xff1a; 1&#xff09;ZYNQ全称&#xff1a;ZYNQ7000 All Pgrammable SoC 2&#xff09;SoC:system on chips(片上系统)&#xff0c;对比集成电路的SoB&#xff08;system on board&#xff09; 3&#xff09;ARM&#xff1a;处理器…...

es6+和css3新增的特性有哪些

一&#xff1a;ECMAScript 新特性&#xff08;ES6&#xff09; ES6 (2015) - 革命性更新 1&#xff0c;记住的方法&#xff0c;从一个方法里面用到了哪些技术 1&#xff0c;let /const块级作用域声明2&#xff0c;**默认参数**&#xff1a;函数参数可以设置默认值。3&#x…...