当前位置: 首页 > 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 …...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...