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

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

TCP/IP 网络编程 | 服务端 客户端的封装

设计模式 文章目录 设计模式一、socket.h 接口&#xff08;interface&#xff09;二、socket.cpp 实现&#xff08;implementation&#xff09;三、server.cpp 使用封装&#xff08;main 函数&#xff09;四、client.cpp 使用封装&#xff08;main 函数&#xff09;五、退出方法…...

2025-05-08-deepseek本地化部署

title: 2025-05-08-deepseek 本地化部署 tags: 深度学习 程序开发 2025-05-08-deepseek 本地化部署 参考博客 本地部署 DeepSeek&#xff1a;小白也能轻松搞定&#xff01; 如何给本地部署的 DeepSeek 投喂数据&#xff0c;让他更懂你 [实验目的]&#xff1a;理解系统架构与原…...