统计子矩阵(前缀和+双指针)

题目描述

给定一个 N × M 的矩阵 A,请你统计有多少个子矩阵 (最小 1 × 1,最大 N × M) 满足子矩阵中所有数的和不超过给定的整数 K? 

输入格式

第一行包含三个整数 N, M 和 K. 

之后 N 行每行包含 M 个整数,代表矩阵 A.

输出格式

一个整数代表答案。

样例输入

3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

样例输出

19

提示

满足条件的子矩阵一共有 19,包含:

大小为 1 × 1 的有 10 个。

大小为 1 × 2 的有 3 个。

大小为 1 × 3 的有 2 个。

大小为 1 × 4 的有 1 个。

大小为 2 × 1 的有 3 个。

对于 30% 的数据,N, M ≤ 20. 对于 70% 的数据,N, M ≤ 100. 

对于 100% 的数据,1 ≤ N, M ≤ 500; 0 ≤ Ai j ≤ 1000; 1 ≤ K ≤ 250000000.

可以用二维前缀和暴力去写 过70%样例 

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define int long long
using namespace std;
const int N=500;
int a[N][N];
int s[N][N];
signed main()
{int n,m,k;cin>>n>>m>>k;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) cin>>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]+a[i][j]-s[i-1][j-1];}}int sum=0;for(int x1=1;x1<=n;x1++){for(int y1=1;y1<=m;y1++){for(int x2=x1;x2<=n;x2++){for(int y2=y1;y2<=m;y2++){if(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<=k) sum++;else break;}}}}cout<<sum<<endl;return 0;
}

一维前缀和+双指针-->该题跟 在一组数中 问能有多少个区间之和小于k 的做法类似

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=550;
int a[N][N];
int s[N][N];
signed main()
{int n,m,k;cin>>n>>m>>k;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];//计算列的前缀和--一维前缀和s[i][j]=a[i][j]+s[i-1][j];}}int ans=0;for(int i=1;i<=n;i++)//上边界{for(int i1=i;i1<=n;i1++)//下边界{for(int l=1,r=1,sum=0;r<=m;r++){sum+=s[i1][r]-s[i-1][r];//确定右边界while(sum>k){sum-=s[i1][l]-s[i-1][l];//求符合条件的左边界l++;}ans+=r-l+1;}}}cout<<ans<<endl;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/296993.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MySQL InnoDB引擎

InnoDB的逻辑存储结构如下图所示&#xff1a; 存储结构 表空间 表空间是InnoDB存储引擎逻辑结构的最高层&#xff0c; 如果用户启用了参数 innodb_file_per_table(在8.0版本中默认开启) &#xff0c;则每张表都会有一个表空间&#xff08;xxx.ibd&#xff09;&#xff0c;一个…

MySQL 索引底层探索:为什么是B+树?

MySQL 索引底层探索&#xff1a;为什么是B树&#xff1f; 1. 由一个例子总结索引的特点2. 基于哈希表实现的哈希索引3. 高效的查找方式&#xff1a;二分查找4. 基于二分查找思想的二叉查找树5. 升级版的BST树&#xff1a;AVL 树6. 更加符合磁盘特征的B树7. 不断优化的B树&#…

Tailscale:随时随地远程和使用服务器

文章目录 Tailscale是什么&#xff1f;Tailscale能做什么&#xff1f;1、传输文件2、远程开发3、代理 Tailscale怎么用&#xff1f;Windows下安装OpenSSH在线安装离线安装连接SSH服务器 Reference相关阅读 彩蛋&#xff1a;Pycharm远程连接服务器并运行代码 Tailscale是什么&am…

【MySQL】数据库的基本操作

目录 一、数据库的库操作 二、数据库的表操作 一、数据库的库操作 数据库的创建 create database (if not exists) 库名 这里的if not exists 是一个判断用的&#xff0c;如果数据库存在&#xff0c;就不执行语句&#xff0c;如果数据库不存在&#xff0c;则执行该语句。 创建…

npm install node-sass报错

前言 在使用 node-sass 时&#xff0c;你可能会遇到安装 node-sass 时出现各种错误的情况。在本文中&#xff0c;我们将探讨一些常见的 node-sass 安装错误&#xff0c;以及如何解决它们。 无论你是初学者还是有经验的开发者&#xff0c;本文都将为你提供有用的信息和技巧&…

PHP在线加密系统网站源码

源码介绍 PHP在线加密系统网站源码&#xff0c;这个是sg的加密,免费可用(目前)并不会收费 源码说明&#xff1a;下载直接上传即可 下载地址 蓝奏云下载&#xff1a;https://wfr.lanzout.com/i6c331togiji

路由Vue-Router使用

Vue Router 是 Vue.js 的官方路由。它与 Vue.js 核心深度集成&#xff0c;让用 Vue.js 构建单页应用变得轻而易举。 介绍 | Vue Router (vuejs.org) 1. 安装 npm install vue-router4 查看安装好的vue-router 2. 添加路由 新建views文件夹用来存放所有的页面&#xff0c;在…

自动驾驶中各种坐标系辨析

坐标系辨析 0. 地球椭圆体1. 大地坐标系2. eci地心惯性坐标系3. 地心地固坐标系(ECEF坐标系&#xff0c;E系)4. 站心坐标系(ENU坐标系)5. UTM坐标系6. LTM坐标系7. IMU坐标系8. 代码部分8.1 LLA(大地坐标系坐标、经纬度海拔)坐标转LTM系(ENU系)下的三维笛卡尔坐标8.2 LLA坐标转…

Java SE入门及基础(47)

集合框架介绍 集合 来自官方的说明 1. 集合与集合框架 A collection — sometimes called a container — is simply an object that groups multiple elements into a single unit. Collections are used to store, retrieve, manipulate, and communicate aggregate data…

【leetcode C++】滑动窗口

1. LCR 008. 长度最小的子数组 题目 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] &#xff0c;并返回其长度。如果不存在符合条件的子数组&#xff0c;返回 0 。 题目…

Django模板层——三种自定义模板simple_tag、inclusion_tag、filter的用法

目录 1. 前言 2. 前置操作 3. simple_tag 3.1 注意点 4. inclusion_tag 5. filter 6. 结尾 1. 前言 在前后端不分离的模式中&#xff0c;Django的模板语法尤为重要&#xff0c;我们可以动态传入变量&#xff0c;并在前端HTML中进行展示。在变量展示时&#xff0c;会有一…

本地运行github上下载的项目--接Git入门篇

1.了解项目 这是一个基于Spring Boot 和 Mybatis Plus 构建的Java项目&#xff0c;很经典的外卖项目&#xff0c;参考b站的黑马瑞吉外卖。 2.构建项目 SpringBoot项目&#xff0c;首先下载一些常见的项目要求的组件。然后配置如下&#xff1a; 看README&#xff0c;在阅读该…

【数据结构】初识数据结构与复杂度总结

前言 C语言这块算是总结完了&#xff0c;那从本篇开始就是步入一个新的大章——数据结构&#xff0c;这篇我们先来认识一下数据结构有关知识&#xff0c;以及复杂度的相关知识 个人主页&#xff1a;小张同学zkf 若有问题 评论区见 感兴趣就关注一下吧 目录 1.什么是数据结构 2.…

即刻体验 | 使用 Flutter 3.19 更高效地开发

我们已隆重推出全新的 Flutter 版本——Flutter 3.19。此版本引入了专为 Gemini 设计的新 Dart SDK、一个能让开发者对 Widget 动画实现精细化控制的全新 Widget&#xff0c;Impeller 更新带来的渲染性能提升、有助于实现深层链接的工具和对 Windows Arm64 的支持&#xff0c;以…

储能系统--液冷充电枪

前言 随着新能源汽车在市场中的占比不断攀升&#xff0c;续航里程和充电时间成为了制约新能源汽车发展的两个关键因素&#xff0c; 而随着续航里程的增加&#xff0c;电池容量也会相应的增加&#xff0c;充电时间也会加长&#xff0c;大功率快充技术逐渐成为解决续航瓶颈的关键…

golang语言系列:Web框架+路由 之 Echo

云原生学习路线导航页&#xff08;持续更新中&#xff09; 本文是golang语言系列文章&#xff0c;本篇主要对 Echo 框架 的基本使用方法 进行学习 1.Echo是什么 Go 有众多Web框架&#xff0c;Echo 是其中的一个&#xff0c;官网介绍Echo有高性能、可扩展性、极简的特点。使用E…

C++的并发世界(五)——线程状态切换

0.线程状态 初始化&#xff1a;该线程正在被创建&#xff1b; 就绪&#xff1a;该线程在列表中就绪&#xff0c;等待CPU调度&#xff1b; 运行&#xff1a;该线程正在运行&#xff1b; 阻塞&#xff1a;该线程被阻塞挂机&#xff0c;Blocked状态包括&#xff1a;pend&#xff…

vulnhub靶机: DC-9

dc-9靶机下载 将靶机设置为NAT模式&#xff0c;本次实验使用的内网网段为192.168.198.0/24&#xff0c;kali的ip为192.168.198.172 信息搜集 ip主机扫描&#xff1a; nmap -sP 192.168.198.0/24 确定靶机ip为192.168.198.171 主机端口扫描&#xff1a; nmap -T4 -A -v 192…

RAG原理、综述与论文应用全解析

1. 背景 1.1 定义 检索增强生成 (Retrieval-Augmented Generation, RAG) 是指在利用大语言模型回答问题之前&#xff0c;先从外部知识库检索相关信息。 早在2020年就已经有人提及RAG的概念&#xff08;paper&#xff1a;Retrieval-augmented generation for knowledge-inten…

LlamaIndex——RAG概述

文章目录 一、使用LLM1. 模型2. 词嵌入3. Prompt 二、加载1. 加载2. 转换&#xff08;1&#xff09;高级API&#xff08;2&#xff09;低级API 三、索引/EmbeddingTop K Retrieval 四、存储五、查询六、评估1. 生成结果质量评估2. 检索结果评估 RAG&#xff08;检索增强生成&am…