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

796. 子矩阵的和(二维前缀和)

题目:

796. 子矩阵的和 - AcWing题库

 

思路: 

1.暴力搜索(搜索时间复杂度为O(n2),很多时候会超时)

2. 前缀和(左上角(二维)前缀和):本题特殊在不是直接求前n个数的和,而是求矩阵中某个元素左上角所以数的和(包括该元素自己),利用左上角前缀和的运算求子矩阵和。

3.在求左上角前缀和以及由左上角前缀和求子矩阵的过程中都需要运用到容斥原理!!!

代码:

#include<iostream>
#include<cstdio>
using namespace std;
typedef unsigned long long ull;
const int N = 1010;
int n, m, q;
ull a[N][N], s[N][N];//a存储数据,s存储左上前缀和
int main()
{cin >> n >> m >> q;for (int i = 1; i <= n; i++)//入读数据for (int j = 1; j <= m; j++)scanf("%d", &a[i][j]);for (int i = 1; i <= n; i++)//求左上前缀和for (int j = 1; j <= m; j++)s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];//容斥原理while (q--) {ull x1, y1, x2, y2;scanf("%llu%llu%llu%llu", &x1, &y1, &x2, &y2);printf("%lld\n", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);//容斥原理}
}

相关文章:

796. 子矩阵的和(二维前缀和)

题目&#xff1a; 796. 子矩阵的和 - AcWing题库 思路&#xff1a; 1.暴力搜索&#xff08;搜索时间复杂度为O(n2)&#xff0c;很多时候会超时&#xff09; 2. 前缀和&#xff08;左上角&#xff08;二维&#xff09;前缀和&#xff09;&#xff1a;本题特殊在不是直接求前…...

利用ChatGPT进行股票走势分析

文章目录 1. 股票分析2. 技巧分析3. 分析技巧21. 股票分析 这张图片显示了一个股票交易软件的界面。以下是根据图片内容的一些解读: 股票代码: 图片右上角显示的代码是“600517”,这是股票的代码。 图形解读: 该图展示了股票的日K线图。其中,蜡烛图表示每日的开盘、收盘、最…...

万字解析设计模式之单例模式

一、概述 1.1简介 单例模式&#xff08;Singleton Pattern&#xff09;是 Java 中最简单的设计模式之一。这种类型的设计模式属于创建型模式&#xff0c;它提供了一种创建对象的最佳方式。 这种模式涉及到一个单一的类&#xff0c;该类负责创建自己的对象&#xff0c;同时确保…...

vue2.x 二次封装element ui 中的el-dialog

在做后台管理系统的时候&#xff0c;dialog组件是我们使用频率比较高的组件&#xff0c;但是有一些需求现有的组件是不满足的。因此会需要我们做二次封装。 组件本身的属性我们保留&#xff0c;只需要根据需求添加&#xff0c;然后在使用的时候props去拿取使用就可以了。 本次遇…...

ssh连接Ubuntu虚拟机出现connection reset by ip地址 port 22怎么解决

使用前提&#xff1a;我是用Windows去连接安装在本机的Ubuntu虚拟机的时候出现的这个问题。 解决的方法&#xff1a;我使用了很多网络上方法&#xff0c;都没有用&#xff0c;发现我把IP地址搞错了 请继续看下去&#xff0c;因为有可能你会错过解决的方法。 在Windows网络连…...

树莓派4B安装ffmpeg

环境&#xff1a; piraspberrypi:~/x264 $ lsb_release -aNo LSB modules are available.Distributor ID: RaspbianDescription: Raspbian GNU/Linux 10 (buster)Release: 10Codename: buster 装H264 git clone --depth 1 https://code.videolan.org/video…...

LeetCode|动态规划|1035. 不相交的线 、53. 最大子数组和

目录 一、1035. 不相交的线 1.题目描述 2.解题思路 3.代码实现 二、53. 最大子数组和 1.题目描述 2.解题思路 3.代码实现&#xff08;动态规划解法&#xff09; 一、1035. 不相交的线 1.题目描述 在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。 现…...

一体式IO模块:汽车行业的数字化转型助推器

随着市场经济需求的不断增长&#xff0c;汽车行业的自动化和智能化已经成为行业发展的必然趋势。在这个背景下&#xff0c;汽车行业的工作流程变得越来越复杂&#xff0c;工业机器人的广泛应用为汽车生产提供了强有力的支持&#xff0c;它们扮演着装配工、操作工、焊接工等多种…...

OpenCV官方教程中文版 —— Hough 直线变换

OpenCV官方教程中文版 —— Hough 直线变换 前言一、原理二、OpenCV 中的霍夫变换三、Probabilistic Hough Transform 前言 目标 • 理解霍夫变换的概念 • 学习如何在一张图片中检测直线 • 学习函数&#xff1a;cv2.HoughLines()&#xff0c;cv2.HoughLinesP() 一、原理…...

【Axure高保真原型】百分比堆叠柱状图

今天和大家分享百分比堆叠柱状图的的原型模板&#xff0c;鼠标移入堆叠柱状图后&#xff0c;会显示数据弹窗&#xff0c;里面可以查看具体项目对应的数据和占比。那这个原型模板是用中继器制作的&#xff0c;所以使用也很方便&#xff0c;只需要在中继器表格里维护项目数据信息…...

Vue.js中的双向数据绑定(two-way data binding)

聚沙成塔每天进步一点点 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 欢迎来到前端入门之旅&#xff01;感兴趣的可以订阅本专栏哦&#xff01;这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域的朋友们量身打造的。无论你是完全的新手还是有一些基础的开发…...

TFN 2.5G SDH传输分析仪 FT100-D300S

今天给大家带来一款TFN 2.5G SDH传输分析仪--TFN FT100-D300S. D300S SDH测试模块&#xff0c;是FT100智能网络测试平台产品家族的一部分&#xff0c;是一个坚固耐用、锂电池超长供电的传统PDH/SDH测试解决方案&#xff0c;支持2.5Gbps到2.048Mbps速率的传输链路测试。支持在线…...

电脑录像功能在哪?一文帮你轻松破解

“电脑录像功能在哪里呀&#xff1f;最近因工作上的原因&#xff0c;需要使用电脑来录像&#xff0c;但是找了一上午都找不到在哪里&#xff0c;眼看已经快没时间了&#xff0c;现在真的很急&#xff0c;希望大家帮帮我。” 电脑已经成为了人们生活和工作中必不可少的工具&…...

基于长短期神经网络的可上调容量PUP预测,基于长短期神经网络的可下调容量PDO预测,LSTM可调容量预测

目录 背影 摘要 代码和数据下载:基于长短期神经网络的可上调容量PUP预测,基于长短期神经网络的可下调容量PDO预测,LSTM可调容量预测(代码完整,数据齐全)资源-CSDN文库 https://download.csdn.net/download/abc991835105/88230834 LSTM的基本定义 LSTM实现的步骤 基于长短…...

站群服务器有哪些优势?

站群服务器有哪些优势&#xff1f; 站群服务器是单独为一个网站或者多个网站配置独立IP的一种服务器。企业或是用户如果想组建多个网站的话就需要用站群服务器了。 站群服务器可以提高搜索引擎多个网站的关注度,提高网站文章的收录以及网站文章的访问量。站群服务器有哪些优势…...

故障诊断模型 | Maltab实现LSTM长短期记忆神经网络故障诊断

文章目录 效果一览文章概述模型描述源码设计参考资料效果一览 文章概述 故障诊断模型 | Maltab实现LSTM长短期记忆神经网络故障诊断 模型描述 长短记忆神经网络——通常称作LSTM,是一种特殊的RNN,能够学习长的依赖关系。 他们由Hochreiter&Schmidhuber引入,并被许多人进行了…...

【WSL 2】Windows10 安装 WSL 2,并配合 Windows Terminal 和 VSCode 使用

【WSL 2】Windows10 安装 WSL 2&#xff0c;并配合 Windows Terminal 和 VSCode 使用 1 安装 Windows Terminal2 安装 WSL 23 在 Windows 文件资源管理器中打开 WSL 项目4 在 VSCode 中使用 WSL 24.1 必要准备4.2 从 VSCode 中 Connect WSL4.3 从 Linux 中打开 VSCode 1 安装 W…...

DbVisualizer和DBeaver启动不来,启动报错

启动报错 大多数启动报错都是因为你没有用管理员身份运行程序&#xff0c;提示的错误都是八竿子打不着的什么jdk、jvm问题。 比如DbVisualizer提示什么jvm配置参数&#xff0c;实际dbvis.exe 用管理员身份打开即可&#xff08;右键 dbvis.exe->属性->兼容性->勾上 “…...

sftp连接远程服务器命令

...

el-select 、el-option 常见用法

<template> <div> // 可以多选 // 添加小叉&#xff0c;点击清空选择器 <el-select v-model"selectedValue" multiple disabled clearable filterable > <el-option …...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...