AcWing 4405. 统计子矩阵:做题笔记

目录

暴力思路 

代码

前缀和+双指针

代码

解释

推荐博客


这道题的主要思路就是枚举所有的子矩阵,判断符合条件的子矩阵的个数。

暴力思路 

我服了,其实我最开始没有想到 :枚举所有的子矩阵 这样一个很有总结性的要点。

我是想着哦我先知道这道题是考二维前缀和的,然后与模板不同的是,这里并没有给出(额也不算没有给出吧)一维前缀和里面 l r 边界中的 l, 这样形容可以理解嘛?像激光炸弹那道题里:

这句话就是给出了左上角的点,我们知道二维前缀和求某个子矩阵的和就是用前缀和数组中右下角-左上角。 

但这道题里没有直接说,我看样例解释之后明白他是需要遍历所有1*1/1*2/...2*1/2*2...,这样,然后我觉得在正常的求某个子矩阵的和的基础上,需要在原来的两层循环内在遍历(1*1/1*2/...2*1/2*2...)这些所有的可能,然后就套了4层循环。写了暴力。

我的暴力是这样写出来的😂哎甚至是暴力都写得很艰难啊🥀🤣

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=510;
int q[N][N];
int n,m,k;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m>>k;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>q[i][j];
			q[i][j]+=q[i-1][j]+q[i][j-1]-q[i-1][j-1];
			//cout<<q[i][j]<<" ";
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(int z=1;z<=i;z++)
			{
				for(int y=1;y<=j;y++)
				{
					int t=q[i][j]-q[z-1][j]-q[i][y-1]+q[z-1][y-1];
				
					if(t<=k)
					{
						cnt++;
					}
				}
			}
		}
	}
	cout<<cnt;
	return 0;
}

因为写了四层循环,500^4,肯定会超时了。

这样是能过6/10个数据,真比赛写到这就算了吧😂别的我也写不出来doge(流下了苦涩的眼泪😂)

前缀和+双指针

这个先看代码把

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=510;
int n,m,k;
int q[N][N];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>q[i][j];
			q[i][j]+=q[i-1][j];//计算出每一列的前缀和矩阵 
		}
	}
	long long cnt=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)//枚举上下边界 
		{
			for(int l=1,r=1,sum=0;r<=m;r++)//左右边界的滑动窗口 
			{
				//当符合题目所说的<=k时,我们就拓宽右边界 
				sum+=q[j][r]-q[i-1][r];//添加上r边界端点的子矩阵的和 
				//不符合的时候,我们就要把左边界向右移动 
				while(sum>k)
				{
					sum-=q[j][l]-q[i-1][l];//减去移出去的左端点处的和
					l++;
				}
				//每次窗口的移动所得到的满足条件子矩阵的个数 =右边界 r 减去左边界 l 再加上 1
				cnt+=r-l+1;
			}
		}
	 } 
	cout<<cnt;
	return 0;
}

解释

这里我们的思路是:

计算出这个二维矩阵每一列的前缀和的二维矩阵

我们可以把这个二维矩阵的每一列 看作 一维前缀和数组中的每一位数字,这个数字实际代表的是一列的前缀和。

我们想要判断这个一维数组所有的子区间是否符合题目条件,

①要么我们暴力枚举所有的子区间:

// 如果计算a数组所有子区间的和,p数组为其预处理出的前缀和
//(这里用前缀和算是为了简写,主要突出两种写法大框架上的区别,否则最内层还有一层计算子区间和的循环)

for(int l=1; l<=n; l++)
{
    for(int r=i; r<=n; r++)
    {
        sum=p[r]-p[l-1];
        // 按题目要求对 sum 进行判断
    }
}

在暴力枚举的方法中,我们需要枚举所有可能的子区间,然后对每个子区间进行检查。这通常需要两层循环,第一层循环枚举子区间的起始位置,第二层循环枚举子区间的结束位置。然后在这两层循环内部,我们计算子区间的和,并进行判断。 

②要么就是利用滑动窗口:

int l = 1, r = 1, sum = 0;

// 使用 for 循环遍历数组
for (r= 1; r < n; r++) {
    // 将右边界的元素加入窗口
    sum += a[r];
    // 使用 while 循环移动左边界,直到窗口内的和满足条件
    while (sum > k && l < r) {
        sum -= a[l];
        l++;
    }
    //对窗口内的和进行判断
}

让这个窗口在数组上滑动,每次滑动都会有一个元素进入窗口,同时有一个元素离开窗口。通过这种方式,我们可以在每次窗口滑动时,快速地更新窗口内的信息,而不需要对整个窗口进行重新计算。

(暴力和滑动窗口的区别主要在外层的两个循环上,而不在于计算这些和上,因为是正是由于外层的两层循环才导致了重复计算的和。)

在每一种确定的上下边界里,通过滑动窗口调整左右边界,这样就把两层循环降成一层。

因此我们每次对这个一维数组的边界的变动就会构成 r-l+1 个不同的子矩阵

我们拓宽右边界,也就是把右端点添加到序列中,从 l~r 的每一个元素加上了 r 都形成了一个新的子区间,在二维里也就是都形成了一个新的子矩阵。因此新增加的包含该列的新的子矩阵的数量就是r-l+1即区间内元素数量

我们在最外层需要有两个for循环一层 i 循环掌管上边界,一层 j 循环掌管下边界,这个下边界是>=上边界的,因此它的初值可以直接从 i 开始。这样就保证了遍历到所有的子矩阵

推荐博客

蓝桥杯2022年第十三届省赛真题-统计子矩阵

我刚开始一直不明白怎么回事,看了这个博主的注释一下清晰了。 推荐看一下


写到这里,感觉好难啊呜呜🥀🥀看了超长时间才理解了优化的

有问题欢迎指出,一起加油!!!

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

重读Java设计模式: 深入探讨建造者模式,构建复杂对象的优雅解决方案

引言 在软件开发中&#xff0c;有时需要构建具有复杂结构的对象&#xff0c;如果直接使用构造函数或者 setter 方法逐个设置对象的属性&#xff0c;会导致代码变得冗长、难以维护&#xff0c;并且容易出错。为了解决这个问题&#xff0c;我们可以使用建造者模式。 一、建造者…

Jamba LLM模型:破解大型上下文窗口挑战的AI新星

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

使用Postman进行websocket接口测试

因为最近要搞关于基于AI的文本接口测试.需要用到websocket协议,于是看了一下发现postman也可以测而且很方便 位置 File->New->WebSocket 可以看到不止WebSocket还支持其他的各种协议 使用 首先先点击connect进行连接 连接成功之后可以选择多种文本格式添加请求参数 每…

打开DICOM文件需要注意到的点

DICOM图片用来存储医学信息 我一般处理的是图像信息&#xff0c;总结一下踩过的坑 打开DICOM文件需要注意到的点 DICOM图片使用python进行打开一定要注意窗口问题&#xff0c;dicom文件里面存储了很多其他的附加信息&#xff0c;不仅仅是图片&#xff0c;其中最重要的一个条就…

力扣刷题Days29-128.最长连续数列(js)

目录 1&#xff0c;题目 2&#xff0c;代码 2.1自己实现 2.2哈希表 3&#xff0c;学习与收获 枚举思想&#xff1a; 遍历的核心逻辑 碎碎念 本题 先是想到利用数组排序&#xff0c;从而简化遍历处理逻辑&#xff0c;再在提交错误提醒的情况下&#xff0c;考虑到数组中存…

Tab切换(Html+JavaScript+Css)

1.CSS样式 <style>* {margin: 0;padding: 0;}.tab {width: 590px;height: 340px;margin: 20px;border: 1px solid #e4e4e4;margin-left: 300px;}.tab-nav {width: 100%;height: 60px;line-height: 60px;display: flex;justify-content: space-between;}.tab-nav h3 {font…

Zeppelin安装

Zeppelin是一个基于Web的开源数据分析可视化工具&#xff0c;它提供了一个交互式的笔记本界面&#xff0c;用于在大数据环境中进行数据探索、数据分析、数据可视化和协作。Zeppelin的主要特点包括多语言支持、可视化功能、数据共享和协作&#xff0c;以及扩展性。它支持多种编程…

C++ 数组 结构编程题

一 求100以内的所有素数 /* * 需要标记2~100 之间的数是否处理 * 用数组&#xff0c;初始为0 表示都是素数&#xff0c;如果 判断为合数则置为1过用 */ #include<stdio.h> #include<math.h> int main() {const int n 100;int isPrim[n 1] { 0 };int i, j;for (…

C++ MFC

C是一种静态数据类型检查的、支持多重编程范式的程序设计语言&#xff0c;支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等泛型程序设计的多种程序设计风格。 MFC(Microsoft Foundation Classes)&#xff0c;是一个微软公司提供的类库&#xff0c;以C类的形式封装…

JAVAEE之CSS

1.CSS 是什么&#xff1f; 层叠样式表 (Cascading Style Sheets). CSS 能够对网页中元素位置的排版进行像素级精确控制, 实现美化页面的效果. 能够做到页面的样式和结构分离. 1.1 CSS和HTML的区别 CSS&#xff0c;全称为层叠样式表(Cascading Style Sheets)&#xff0c;是…

【Spring Boot 源码学习】ConditionEvaluationReport 日志记录上下文初始化器

《Spring Boot 源码学习系列》 ConditionEvaluationReport 日志记录上下文初始化器 一、引言二、往期内容三、主要内容3.1 源码初识3.2 ConditionEvaluationReport 监听器3.3 onApplicationEvent 方法3.4 条件评估报告的打印展示 四、总结 一、引言 上篇博文《共享 MetadataRe…

redis和数据库数据不一直问题,缓存常见的三大问题

文章目录 数据一致性缓存常见问题缓存穿透缓存击穿缓存雪崩 数据一致性 1 思路 查询数据的时候&#xff0c;如果缓存未命中&#xff0c;则查询数据库&#xff0c;将数据写入缓存设置超时时间修改数据时&#xff0c;先修改数据库&#xff0c;在删除缓存。 2 代码实现 修改更…

【原创】基于分位数回归的卷积长短期结合注意力机制的神经网络(CNN-QRLSTM-Attention)回归预测的MATLAB实现

基于分位数回归的卷积长短期结合注意力机制的神经网络&#xff08;CNN-QRLSTM-Attention&#xff09;是一种用于时间序列数据预测的深度学习模型。该模型结合了卷积神经网络&#xff08;CNN&#xff09;、长短期记忆网络&#xff08;LSTM&#xff09;和注意力机制&#xff08;A…

P1803 凌乱的yyy / 线段覆盖(贪心)

思路&#xff1a; 这道题让求区间覆盖&#xff0c;它要求只能一个一个的区间&#xff0c;先对n个区间进行排序&#xff0c;按照区间的结束点前后进行排序。所以从后往前看结束时间点&#xff0c;如果下一个的起点在前一个的结束点之后&#xff0c;则数量加1。 代码&#xff1a…

Python进阶编程 --- 1.类和对象

文章目录 第一章&#xff1a;1.初始对象1.1 使用对象组织数据1.2 类的成员方法1.2.1 类的定义和使用1.2.2 创建类对象1.2.3 成员变量和成员方法1.2.4 成员方法的定义语法1.2.5 注意事项 1.3 类和对象1.3.1 基于类创建对象 1.4 构造方法1.5 其他内置方法1.5.1 魔术方法str字符串…

鸿蒙OS开发实战:【网络管理HTTP数据请求】

一、场景介绍 应用通过HTTP发起一个数据请求&#xff0c;支持常见的GET、POST、OPTIONS、HEAD、PUT、DELETE、TRACE、CONNECT方法。 二、 接口说明 HTTP数据请求功能主要由http模块提供。 使用该功能需要申请ohos.permission.INTERNET权限。 涉及的接口如下表&#xff0c;…

python爬取B站视频

参考&#xff1a;https://cloud.tencent.com/developer/article/1768680 参考的代码有点问题&#xff0c;请求头需要修改&#xff0c;上代码&#xff1a; import requests import re # 正则表达式 import pprint import json from moviepy.editor import AudioFileClip, Vid…

QT初识(2)

QT初识&#xff08;2&#xff09; 创建好项目之后&#xff0c;多了些什么东西&#xff1f;main.cppwidget.hwidget.cppwidget.ui.pro项目工程文件 我们今天来继续了解QT。如果没看过上一次QT初识的小伙伴可以点击这里&#xff1a; https://blog.csdn.net/qq_67693066/article/d…

STM32的DMA

DMA(Direct memory access)直接存储器存取,用来提供在外设和存储器之间或者存储 器和存储器之间的高速数据传输&#xff0c;无须CPU干预&#xff0c;数据可以通过DMA快速地移动&#xff0c;这就节 省了CPU的资源来做其他操作。 STM32有两个DMA控制器共12个通道(DMA1有7个通道…

基于YOLOV8+Pyqt5光伏太阳能电池板目标检测系统

1、YOLOV8算法 YOLOv8 是当前效果较好的目标检测 算法&#xff0c;它的核心网络来源于 DarkNet-53&#xff0c;该网络初次在 YOLOv3[11] 中被引入&#xff0c;并深受 ResNet[12] 的影响。DarkNet-53 使用了残差机制&#xff0c;并连续添加了卷积模块来加强其功能性。 这 53 层…