【单调队列单调栈专题】【蓝桥杯备考训练】:矩形牛棚、单调栈、滑动窗口、子矩阵、最大子序和、烽火传递【已更新完成】

本文主要是介绍【单调队列单调栈专题】【蓝桥杯备考训练】:矩形牛棚、单调栈、滑动窗口、子矩阵、最大子序和、烽火传递【已更新完成】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1、矩形牛棚(usaco training 6.1)

思路:

预处理的过程:

判断左右边界的过程:

代码:

2、单调栈(单调栈模板)

思路:

基本步骤:

1、维护单调性

2、处理要求的操作

3、入栈

代码:

3、滑动窗口(单调队列模板)

思路:

基本步骤(以求最大值为例):

1、维护单调性(在尾部做处理)

2、入队

3、判断是否滑出窗口,滑出则hh++

4、做要求的处理

代码:

4、子矩阵(第十四届蓝桥杯省赛C++ C组、第十四届蓝桥杯省赛Java C组/研究生组、第十四届蓝桥杯省赛Python A组)

思路:

固定左右边界进行枚举的过程:

实现得到滑动窗口最大值最小值的函数:

代码:

5、最大子序和(《算法竞赛进阶指南》)

思路:

滑动窗口中维护前缀和的单调性的步骤:

代码:

6、烽火传递(NOIP2010提高组初赛、《信息学奥赛一本通》)

思路:

维护单调性的步骤:

代码:


1、矩形牛棚(usaco training 6.1)

作为一个资本家,农夫约翰希望通过购买更多的奶牛来扩大他的牛奶业务。

因此,他需要找地方建立一个新的牛棚。

约翰购买了一大块土地,这个土地可以看作是一个 R行(编号 1∼R)C列(编号 1∼C)的方格矩阵。

不幸的是,他发现其中的部分方格区域已经被破坏了,因此他无法在整个 R×C 的土地上建立牛棚。

经调查,他发现共有 P 个方格内的土地遭到了破坏。

建立的牛棚必须是矩形的,并且内部不能包含被破坏的土地。

请你帮约翰计算,他能建造的最大的牛棚的面积是多少。

输入格式

第一行包含三个整数 R,C,P。

接下来 P 行,每行包含两个整数 r,c,表示第 r 行第 c 列的方格区域内土地是被破坏的。

输出格式

输出牛棚的最大可能面积。

数据范围

1≤R,C≤3000
0≤P≤30000
1≤r≤R1
1≤c≤C1

输入样例:
3 4 2
1 3
2 1
输出样例:
6
思路:

对于每行(预处理好每个方块上面最多能用的方块的个数),枚举其中的每列,分别判断左右两边第一列比该行少的位置,然后底乘高算出面积,维护最大值即可

预处理的过程:
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(g[i][j]==0){h[i][j]=h[i-1][j]+1;}}//记录这一位置上面能用的格子是多少 
判断左右边界的过程:
int work(int a[])
{a[0]=-1,a[m+1]=-1;int tt=0;//枚举左边第一个比这个位置上面能用的格子少的左边界 stk[++tt]=0;//把左边界加进去 for(int i=1;i<=m;i++){while(a[i]<=a[stk[tt]])tt--;//栈顶元素大于等于当前元素的话弹出栈顶 l[i]=stk[tt];stk[++tt]=i; } tt=0;stk[++tt]=m+1;for(int i=m;i>=1;i--){while(a[stk[tt]]>=a[i])tt--;r[i]=stk[tt];stk[++tt]=i;}int res=0;for(int i=1;i<=m;i++){res=max(res,a[i]*(r[i]-l[i]-1));}return res;
}
代码:
#include<bits/stdc++.h>using namespace std;const int N=3010;int n,m,p;int g[N][N],h[N][N];int l[N],r[N];int stk[N];int work(int a[])
{a[0]=-1,a[m+1]=-1;int tt=0;//枚举左边第一个比这个位置上面能用的格子少的左边界 stk[++tt]=0;//把左边界加进去 for(int i=1;i<=m;i++){while(a[i]<=a[stk[tt]])tt--;//栈顶元素大于等于当前元素的话弹出栈顶 l[i]=stk[tt];stk[++tt]=i; } tt=0;stk[++tt]=m+1;for(int i=m;i>=1;i--){while(a[stk[tt]]>=a[i])tt--;r[i]=stk[tt];stk[++tt]=i;}int res=0;for(int i=1;i<=m;i++){res=max(res,a[i]*(r[i]-l[i]-1));}return res;
}int main()
{cin>>n>>m>>p;for(int i=0;i<p;i++){int r,c;cin>>r>>c;g[r][c]=1;//标记为破坏 }for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(g[i][j]==0){h[i][j]=h[i-1][j]+1;}}//记录这一位置上面能用的格子是多少 int res=0;for(int i=1;i<=n;i++){res=max(res,work(h[i]));}cout<<res;return 0;
} 

2、单调栈(单调栈模板)

给定一个长度为 N 的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1。

输入格式

第一行包含整数 N,表示数列长度。

第二行包含 N 个整数,表示整数数列。

输出格式

共一行,包含 N 个整数,其中第 i 个数表示第 i 个数的左边第一个比它小的数,如果不存在则输出 −1。

数据范围

1≤N≤1e5
1≤数列中元素≤1e9

输入样例:
5
3 4 2 7 5
输出样例:
-1 3 -1 2 2
思路:

经典单调栈模板

基本步骤:
1、维护单调性
while(tt>0 && s[tt]>=x)tt--;
2、处理要求的操作
if(tt<=0)cout<<"-1"<<" ";else cout<<s[tt]<<" ";
3、入栈
s[++tt]=x;
代码:
#include<bits/stdc++.h>using namespace std;const int N = 1e5 +5 ;int tt;
int s[N];int main()
{int n;cin>>n;while(n--){int x;cin>>x;while(tt>0 && s[tt]>=x)tt--;if(tt<=0)cout<<"-1"<<" ";else cout<<s[tt]<<" ";s[++tt]=x;}	return 0;
}

3、滑动窗口(单调队列模板)

给定一个大小为 n≤1e6 的数组。

有一个大小为 k 的滑动窗口,它从数组的最左边移动到最右边。

你只能在窗口中看到 k 个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子:

该数组为 [1 3 -1 -3 5 3 6 7],k 为 3。

窗口位置最小值最大值
[1 3 -1] -3 5 3 6 7-13
1 [3 -1 -3] 5 3 6 7-33
1 3 [-1 -3 5] 3 6 7-35
1 3 -1 [-3 5 3] 6 7-35
1 3 -1 -3 [5 3 6] 736
1 3 -1 -3 5 [3 6 7]37

你的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数 n 和 k,分别代表数组长度和滑动窗口的长度。

第二行有 n 个整数,代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出,从左至右,每个位置滑动窗口中的最小值。

第二行输出,从左至右,每个位置滑动窗口中的最大值。

输入样例:
8 3
1 3 -1 -3 5 3 6 7
输出样例:
-1 -3 -3 -3 3 3
3 3 5 5 6 7
思路:

经典单调队列模板

基本步骤(以求最大值为例):
1、维护单调性(在尾部做处理)
while(hh<=tt && a[i]>dq[tt])tt--;
2、入队
dq[++tt]=a[i];
3、判断是否滑出窗口,滑出则hh++
if(i-k>=0 && dq[hh]==a[i-k])hh++;
4、做要求的处理
if(i+1>=k)cout<<dq[hh]<<" ";	
代码:
#include<bits/stdc++.h>using namespace std;const int N=1e6+5;int n,k;int tt=-1,hh;
int dq[N],a[N];int main()
{cin>>n>>k;for(int i=0;i<n;i++)scanf("%d",&a[i]);//求窗口最小值 for(int i=0;i<n;i++){while(hh<=tt && a[i]<dq[tt])tt--;dq[++tt]=a[i];//if(i-k>=0 && dq[hh]==a[i-k])hh++;//队头一定是最小的if(i+1>=k)cout<<dq[hh]<<" "; }	cout<<endl;//求最大值tt=-1,hh=0;for(int i=0;i<n;i++){while(hh<=tt && a[i]>dq[tt])tt--;dq[++tt]=a[i];if(i-k>=0 && dq[hh]==a[i-k])hh++;if(i+1>=k)cout<<dq[hh]<<" ";	} return 0;
}

4、子矩阵(第十四届蓝桥杯省赛C++ C组、第十四届蓝桥杯省赛Java C组/研究生组、第十四届蓝桥杯省赛Python A组)

给定一个 n×m(n 行 m 列)的矩阵。

设一个矩阵的价值为其所有数中的最大值和最小值的乘积。

求给定矩阵的所有大小为 a×b (a 行 b 列)的子矩阵的价值的和。

答案可能很大,你只需要输出答案对 998244353998244353 取模后的结果。

输入格式

输入的第一行包含四个整数分别表示 n,m,a,b相邻整数之间使用一个空格分隔。

接下来 n行每行包含 m 个整数,相邻整数之间使用一个空格分隔,表示矩阵中的每个数 A[i],[j]。

输出格式

输出一行包含一个整数表示答案。

数据范围

对于 40%40% 的评测用例,1≤n,m≤100
对于 70%70% 的评测用例,1≤n,m≤500;
对于所有评测用例,1≤a≤n≤1000,1≤b≤m≤1000,1≤Ai,j≤1e9。

输入样例:
2 3 1 2
1 2 3
4 5 6
输出样例:
58
样例解释

1×2+2×3+4×5+5×6=581×2+2×3+4×5+5×6=58。

思路:

固定左右边界进行枚举,这时候从上上边界往下边界枚举,每次在每个区域中在每行的最小值中选出最小的,在每行的最大值中选出最大的,这个区域的最大值乘最小值就是该矩阵的价值

固定左右边界进行枚举的过程:
	for(int i=b-1;i<m;i++)//固定好列区间 {for(int j=0;j<n;j++)A[j]=maxr[j][i];//每行:把每个窗口最大的数取出来getmax(A,B,n,a);//存到B中 for(int j=0;j<n;j++)A[j]=minr[j][i];//每行:把每个窗口最小的数取出来 getmin(A,C,n,a);//存到C中 for(int j=a-1;j<n;j++)	{res=(res+(LL)B[j]*C[j])%MOD;}}
实现得到滑动窗口最大值最小值的函数:
void getmin(int a[],int b[],int total,int lenth)
{int tt=-1,hh=0;for(int i=0;i<total;i++){//判断元素是否滑出窗口 if(hh<=tt && q[hh]<=i-lenth)hh++;//判断新元素和旧元素的大小关系确保队列单调while(hh<=tt && a[i]<=a[q[tt]])tt--; 	//入队 q[++tt]=i;//把最值交给存储数组 (队头一定是最小的) if(i>=lenth-1)b[i]=a[q[hh]];//i>=k-1表示滑动窗口形成}
}void getmax(int a[],int b[],int total,int lenth)
{int tt=-1,hh=0;for(int i=0;i<total;i++){if(hh<=tt && q[hh]<=i-lenth)hh++;while(hh<=tt && a[i]>=a[q[tt]])tt--;q[++tt]=i;//队头一定是最大的,赋值给b if(i>=lenth-1)b[i]=a[q[hh]];}
}
代码:
#include<bits/stdc++.h>using namespace std;const int N=1010;int n,m,a,b; int g[N][N],minr[N][N],maxr[N][N]; int q[N];typedef long long LL;const int MOD=998244353;void getmin(int a[],int b[],int total,int lenth)
{int tt=-1,hh=0;for(int i=0;i<total;i++){//判断元素是否滑出窗口 if(hh<=tt && q[hh]<=i-lenth)hh++;//判断新元素和旧元素的大小关系确保队列单调while(hh<=tt && a[i]<=a[q[tt]])tt--; 	//入队 q[++tt]=i;//把最值交给存储数组 (队头一定是最小的) if(i>=lenth-1)b[i]=a[q[hh]];//i>=k-1表示滑动窗口形成}
}void getmax(int a[],int b[],int total,int lenth)
{int tt=-1,hh=0;for(int i=0;i<total;i++){if(hh<=tt && q[hh]<=i-lenth)hh++;while(hh<=tt && a[i]>=a[q[tt]])tt--;q[++tt]=i;//队头一定是最大的,赋值给b if(i>=lenth-1)b[i]=a[q[hh]];}
}int main()
{cin>>n>>m>>a>>b;for(int i=0;i<n;i++)for(int j=0;j<m;j++)scanf("%d",&g[i][j]);//for(int i=0;i<n;i++)//for(int j=0;j<m;j++)printf("%d",g[i][j]);//预处理出来每一行中滑动窗口的最值 for(int i=0;i<n;i++){getmin(g[i],minr[i],m,b);getmax(g[i],maxr[i],m,b);}int res=0;int A[N],B[N],C[N];for(int i=b-1;i<m;i++)//固定好列区间 {for(int j=0;j<n;j++)A[j]=maxr[j][i];//每行:把每个窗口最大的数取出来getmax(A,B,n,a);//存到B中 for(int j=0;j<n;j++)A[j]=minr[j][i];//每行:把每个窗口最小的数取出来 getmin(A,C,n,a);//存到C中 for(int j=a-1;j<n;j++)	{res=(res+(LL)B[j]*C[j])%MOD;}}cout<<res;return 0;
}

5、最大子序和(《算法竞赛进阶指南》)

输入一个长度为 n 的整数序列,从中找出一段长度不超过 m 的连续子序列,使得子序列中所有数的和最大。

注意: 子序列的长度至少是 1。

输入格式

第一行输入两个整数 n,m。

第二行输入 n 个数,代表长度为 n 的整数序列。

同一行数之间用空格隔开。

输出格式

输出一个整数,代表该序列的最大子序和。

数据范围

1≤n,m≤300000
保证所有输入和最终结果都在 int 范围内。

输入样例:
6 4
1 -3 5 1 -2 3
输出样例:
7
思路:

前缀和+滑动窗口

滑动窗口中维护前缀和的单调性的步骤:
//s[q[tt]] 即将被减去,当然是越小越好 
//如果s[i](前i个数的和)小于s[q[tt]](前面的前缀和)
//那么s[i]更适合被减去来求后面的前缀和 
while(hh<=tt && s[q[tt]]>=s[i])tt--;
代码:
#include<bits/stdc++.h>using namespace std;const int N=300000+10;int n,m; long long  s[N];int q[N],hh=-1,tt;int main()
{cin>>n>>m;//前缀和 for(int i=1;i<=n;i++){cin>>s[i];s[i]+=s[i-1];}long long res=INT_MIN;for(int i=1;i<=n;i++){//判断是否滑出窗口 if(hh<=tt && q[hh]<=i-m-1)hh++;//保持单调性 //while(hh<=tt &&  )res=max(res,s[i]-s[q[hh]]);//s[q[tt]] 即将被减去,当然是越小越好 //如果s[i](前i个数的和)小于s[q[tt]](前面的前缀和)//那么s[i]更适合被减去来求后面的前缀和 while(hh<=tt && s[q[tt]]>=s[i])tt--;q[++tt]=i;}cout<<res;return 0;
} 

6、烽火传递(NOIP2010提高组初赛、《信息学奥赛一本通》)

烽火台是重要的军事防御设施,一般建在交通要道或险要处。

一旦有军情发生,则白天用浓烟,晚上有火光传递军情。

在某两个城市之间有 n 座烽火台,每个烽火台发出信号都有一定的代价。

为了使情报准确传递,在连续 m 个烽火台中至少要有一个发出信号。

现在输入 n,m 和每个烽火台的代价,请计算在两城市之间准确传递情报所需花费的总代价最少为多少。

输入格式

第一行是两个整数 n,m,具体含义见题目描述;

第二行 n 个整数表示每个烽火台的代价 ai。

输出格式

输出仅一个整数,表示最小代价。

数据范围

1≤m≤n≤2×1e5
0≤ai≤1000

输入样例:
5 3
1 2 5 6 2
输出样例:
4
思路:

动态规划+单调队列

f[i]表示第i个烽火台点燃需要的最小代价

维护单调性的步骤:
//维护单调性
while(hh<=tt && f[i]<=f[q[tt]])tt--;
代码:
#include<bits/stdc++.h>using namespace std;const int N=2e5+10;int n,m; int a[N];int q[N];int hh,tt=-1;
//dp
int f[N];int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}//前0个烽火台的最小代价是0 f[++tt]=0;int res=1e9;for(int i=1;i<=n;i++){//f[i]表示第i个烽火台点燃需要的最小代价//超出i-m范围则不合法 if(q[hh]<i-m)hh++;f[i]=f[q[hh]]+a[i];//维护单调性while(hh<=tt && f[i]<=f[q[tt]])tt--;q[++tt]=i; }for(int i=n-m+1;i<=n;i++)res=min(res,f[i]);cout<<res;return 0;
} 
/*
5 3
1 2 5 6 24*/

这篇关于【单调队列单调栈专题】【蓝桥杯备考训练】:矩形牛棚、单调栈、滑动窗口、子矩阵、最大子序和、烽火传递【已更新完成】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/854819

相关文章

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

hdu1689(线段树成段更新)

两种操作:1、set区间[a,b]上数字为v;2、查询[ 1 , n ]上的sum 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

如何在页面调用utility bar并传递参数至lwc组件

1.在app的utility item中添加lwc组件: 2.调用utility bar api的方式有两种: 方法一,通过lwc调用: import {LightningElement,api ,wire } from 'lwc';import { publish, MessageContext } from 'lightning/messageService';import Ca

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

AI行业应用(不定期更新)

ChatPDF 可以让你上传一个 PDF 文件,然后针对这个 PDF 进行小结和提问。你可以把各种各样你要研究的分析报告交给它,快速获取到想要知道的信息。https://www.chatpdf.com/

软件设计师备考——计算机系统

学习内容源自「软件设计师」 上午题 #1 计算机系统_哔哩哔哩_bilibili 目录 1.1.1 计算机系统硬件基本组成 1.1.2 中央处理单元 1.CPU 的功能 1)运算器 2)控制器 RISC && CISC 流水线控制 存储器  Cache 中断 输入输出IO控制方式 程序查询方式 中断驱动方式 直接存储器方式(DMA)  ​编辑 总线 ​编辑

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s