首页 > 其他分享 >2023ACM暑假训练day 5-单调队列 单调栈

2023ACM暑假训练day 5-单调队列 单调栈

时间：2023-06-30 23:24:01浏览次数：44  
标签：cn 2023ACM leetcode https include com day 单调

目录

DAY 5 单调队列/栈

训练地址：传送门

训练情况简介

早上：A、B、C、D题
下午：E题(未出，看了题解)、F题(暂时没有思路)
晚上：牛客小白月赛75+F、G题
6.30 记
今天仅做了单调栈的题，再练了一下相关题
后面的单调队列有两道都做过了，所以后面有时间记得补

A 题

题意：
给定一个数列，判断每个元素后第一个大于当前元素的下标，没有则为0
思路：
递减单调栈模板题

B 题

题意：
给定一个序列，代表每一只奶牛的高度，判断每一只奶牛在看到比自己高的奶牛前的奶牛数，最后输出总数
思路：
依旧是递减单调栈，与A题类似，但没有那么直接，得自己翻译一下题目

C 题

题意：
给你一个长度为n的序列，让你确定一个区间\([l,r]\)，满足\(1\leq l<r\leq n\)时，该区间内的最大值和次大值的异或和最大
思路：
这题有点妙哈，但也让我理解了单调栈的妙处！利用递减单调栈快速寻找区间的最大值和次大值
我们维护一个递减的单调栈，从前往后遍历。在出栈时，形成了一个序列，且当前元素为最大，栈顶元素为次大，ans统计结果的最大值；在进栈时，也形成了一个序列，当前为次大，栈顶为最大，更新异或最大值。最后输出答案即可。
总之，妙！这比\(O(n^3)\)寻找区间和区间的最大次大爽快多了

D 题

题意：
给你一个长为n的序列，让你确定是否对于所有区间\([l,r]\)，满足\(1\leq l<r\leq n\)时，该区间内的最大值大于等于该区间的和
思路：
依旧是利用递减单调栈存最大值，栈内存序列下标，每次进栈出栈都更新最大值与区间和的大小关系，即可得到答案
这里有个小问题，为什么仅考虑两侧即可？就是为什么进栈出栈的时候考虑就行，那不是有些序列（栈维护最大值递减，非递减则会出栈相应元素）没有考虑到吗？就是为什么仅考虑一个最大值的单左侧是否成立，单右侧是否成立即可？因为，除了当前元素，单左侧的元素满足和\(\leq0\)(因为当前元素值大于单左侧的和)，对于单右侧元素同理，故对于整个左右合并，除了当前元素的和仍小于0，故条件成立，满足题意
而且，从前面往后遍历数组，满足所有最大值的单左侧成立，之后在进栈的时候维护单右侧，使得单右侧依然成立，故整个栈都是成立的。
这题还可以再理解理解，写完代码后才发现里面的妙处！

E 题　未出，题解补

题意：
给你一个长度为n的数组，对于所有区间\([l,r]\)，满足\(1\leq l<r\leq n\)，求解\(\sum_{l=1}^{n-1}{\sum_{r=l+1}^{n}{次大值in [l,r] }}\)
思路：
主要就是对于每一个元素，我们都要考虑其对于最终式子的贡献，ans加上该点的贡献，即可得到最终答案
那么问题来了，怎么快捷地找一个区间的次小值，对于单调栈来说，找区间的最大值，次大值很容易，但是对于所有区间的最小值，次小值，就很吃力了应该，所以单单依靠一个单调栈估计很难求解
自己写的双向链表没法指向第二个大于自己的，，，或者说，想错了

洛谷的题解给了两种做法
做法一：单调栈+st表
很妙！
就是利用单调栈找到当前元素左右最近比自己最大的值，再利用两个st表快速找到左边和右边第二个最近的比当前元素大的数的位置，在统计求解即可
待学习st表和代码实现 实现后打勾 [ ]
做法二：双向链表
很妙！
利用双向链表实现上面思路的st表，直接在代码里给出注释

//>>>Qiansui
#include<map>
#include<set>
#include<list>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<string>
#include<vector>
#include<utility>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<functional>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
#define debug(x) cout << #x << " = " << x << endl
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << endl
//#define int long long

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
	return x*f;
}

using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ull,ull> pull;
typedef pair<double,double> pdd;
/*
difficult...
思路来自洛谷，还在理解中，待摘记
这个从头开始的双向链表
前面的结果递推到后面
妙！
*/
const int maxm=1e5+5,inf=0x3f3f3f3f,mod=998244353;
ll n,a[maxm],L[maxm],R[maxm];

void solve(){
	cin>>n;
	ll t;
	for(int i=1;i<=n;++i){
		cin>>t;
		//对于每个数统计其位于数组中的位置
		a[t]=i;
		//其初始左右即标记为数组中位置的左右，后面会更新
		L[i]=i-1;
		R[i]=i+1;
	}
	ll ans=0;
	for(int i=1;i<=n;++i){//从小到大遍历数，同时更新L和R
		//l、r即为左右最近的比当前数大的下标
		int l=L[a[i]],r=R[a[i]];
		//左边存在区间时，必取左大1和当前，当前为区间次大值
		//再向两边扩展，两边扩展小于当前数的数，可能的区间数即为(左大1-左大2)*(右大-当前)
		if(l>=1) ans+=i*(l-L[l])*(r-a[i]);
		//右边存在区间时，必取右大1和当前，当前为区间次大值
		//再向两边扩展，两边扩展小于当前数的数，可能的区间数即为(右大2-右大1)*(当前-左大)
		if(r<=n) ans+=i*(R[r]-r)*(a[i]-l);
		//删去当前数的影响，因为它不可能成为接下来区间的次小数
		L[r]=l;R[l]=r;
	}
	cout<<ans<<'\n';
	return ;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
//	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

相关资料：
妙哉！Second Sum！ - Acfboy 的博客 - 洛谷博客 (luogu.com.cn)

F 题 未出，题解补

题意：
给你一个长度为n的数组m，要求你再构造一个数组a，满足两个条件：
\(1. 对于所有的i\in[1,n]，有a_i\leq m_i\)
\(2. 满足1的情况下，对于所有的j<i<k\in[1,n]，a数组中不存在a_j>a_i<a_k\)
求在这两个条件下，数组和的最大值？
思路：
题目的意思是，对于你自己构造的数组，不能出现"V形"的样子，肯定是"倒V形"
那么最终可能的数组情况就只有三种情况：单调非递减、单调非递增、中间凸两边凹三种情况
所以我们可以利用单调栈来找前两种情况的最优值，同时记下前缀和后缀和，这是为了方便第三种情况的判断，具体可见代码

//>>>Qiansui
#include<map>
#include<set>
#include<list>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<string>
#include<vector>
#include<utility>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<functional>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
#define debug(x) cout << #x << " = " << x << endl
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << endl
//#define int long long

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
	return x*f;
}

using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ull,ull> pull;
typedef pair<double,double> pdd;
/*
wa一发，思路有问题
题目好像还看错了！j < i < k是对于所有的下标的，而不是局部
那么最终的序列的可能情况：
单调非递增或非递减、中间凸两边凹三种情况
*/
const int maxm=5e5+5,inf=0x3f3f3f3f,mod=998244353;
ll n,a[maxm],l[maxm],r[maxm],ans[maxm];
ll suml[maxm],sumr[maxm];

void solve(){
	cin>>n;
	for(int i=1,j;i<=n;++i){
		cin>>a[i];
		//利用数组模拟单调栈
		j=i-1;
		while(j>0 && a[i]<a[j]){
			j=l[j];
		}
		l[i]=j;
		//更新前缀和
		suml[i]=suml[j]+1ll*(i-j)*a[i];//a[j+1~i]=a[i]
	}
	ll s=0,t;
	for(int i=n,j;i>0;--i){
		//利用数组模拟单调栈
		j=i+1;
		while(j<=n && a[i]<a[j]) j=r[j];
		r[i]=j;
		//更新后缀和
		sumr[i]=sumr[j]+1ll*(j-i)*a[i];//a[i~j-1]=a[i]
		//维护最大值，判断第三种情况的成立性
		if(suml[i]+sumr[i]-a[i]>s){
			s=suml[i]+sumr[i]-a[i];
			t=i;
		}
	}
	for(int i=t-1;i>0;--i){//从t向右维护数组a
		if(a[i]>a[i+1]) a[i]=a[i+1];
	}
	for(int i=t+1;i<=n;++i){//从t向左维护数组a
		if(a[i]>a[i-1]) a[i]=a[i-1];
	}
	for(int i=1;i<=n;++i){
		cout<<a[i]<<" \n"[i==n];
	}
	return ;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
//	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

相关资料：
题解传送门

G 题 看了cf数据，得wa启发

题意：
n个数依次排列，玩家初始位于第一个数上，玩家想抵达最后一个数上，但玩家的移动不是随意的，需要满足三个条件之一，才可以在第 i 和 j 个数上移动 (i < j)
三个条件为：
$1.i+1=j $
\(2. max(h_{i+1},...,h_{j-1})<min(h_i,h_j)\)
\(3. min(h_{i+1},...,h_{j-1})>max(h_i,h_j)\)
题目问你，玩家若最终抵达，最小的移动次数是多少？
思路：
注意不等号是严格不等号，又因为这个题在单调栈，所以判断移动时得注意相同数的影响
一个数组DP统计到达第 i 个数时所需要的最小移动次数
想要移动次数最小，就要充分利用2、3条件
对于第 i 个数，我们可以寻找其前面第一个大于/等于/小于的数，这三个数都可以作为移动的起点，之后利用这些起点更新第 i 个位置的移动最小值，从而递推实现整体最小
最终的答案即为\(dp[n]\)
wa5可能是因为移动的考虑不充分
wa13可能就是重复数的影响

补充内容

单调栈 Monotone Stack

【图解单调栈】两种方法，两张图秒懂
https://leetcode.cn/problems/next-greater-node-in-linked-list/solution/tu-jie-dan-diao-zhan-liang-chong-fang-fa-v9ab/
举例：返回每个元素两侧严格大于它的元素位置（不存在则为 -1 或 n）
如何理解：把数组想象成一列山峰，站在 a[i] 的山顶仰望两侧的山峰，是看不到高山背后的矮山的，只能看到一座座更高的山峰
这就启发我们引入一个底大顶小的单调栈，入栈时不断比较栈顶元素直到找到一个比当前元素大的
技巧：事先压入一个边界元素到栈底，这样保证循环时栈一定不会为空，从而简化逻辑
一些转换：
若区间 [l,r] 的最大值等于 a[r]，则 l 必须 > left[r]
若区间 [l,r] 的最大值等于 a[l]，则 r 必须 < right[l]
这一结论可以用于思考一些双变量的题目

https://oi-wiki.org/ds/monotonous-stack/
https://cp-algorithms.com/data_structures/stack_queue_modification.html

单调栈

矩形系列

字典序最小

贡献法

单调队列 Monotone Queue

两张图秒懂单调队列（Python/Java/C++/Go）
https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/solution/liang-zhang-tu-miao-dong-dan-diao-dui-li-9fvh/
需要不断维护队列的单调性，时刻保证队列元素从大到小或从小到大
前置知识：双指针
以固定窗口大小的区间最大值为例（此时维护的是一个从大到小的单调队列）：
每次向右移动一格左指针，在移动前，如果左指针指向的元素在队首左侧，说明左指针指向的元素小于队首，移动左指针不会改变区间最大值，直接移动左指针即可；
如果左指针指向的就是队首，那么移动左指针会使区间最大值变小（变为单调队列队首之后的那个元素），我们要弹出队首。
这样无论是何种情况，都保证了在移动左指针后，单调队列的队首始终为当前区间的最大值。
https://oi-wiki.org/ds/monotonous-queue/
https://oi-wiki.org/dp/opt/monotonous-queue-stack/
https://cp-algorithms.com/data_structures/stack_queue_modification.html
https://blog.csdn.net/weixin_43914593/article/details/105791217 算法竞赛专题解析（13）：DP优化(3)--单调队列优化
todo https://xyzl.blog.luogu.org/DQ-OP-DP

标签：cn,2023ACM,leetcode,https,include,com,day,单调
From： https://www.cnblogs.com/Qiansui/p/17518013.html

相关文章

  • STD-study-暑假-大一下-PTA-day1
    L1-001#include<iostream>usingnamespacestd;intmain(){cout<<"HelloWorld!"<<endl;return0;}毫无难度L1-002打印沙漏#include<stdio.h>#include<math.h>intmain(){intn;//符号的个数charc;//符号......
  • 闲话 Day13.5
    稍微沾点学术而且闲话不多。难得一见的，我也开始打专题了啊。放在之前大概是完全不做/找几个水题打完跑路的。可能是感觉DP/字符串这边确实啥都不会吧。能够放到专题里面的题大抵质量还是不错的。所以打一打没啥坏处。相对来说，可能打专题比打模拟赛的用处大一点（?）然而，不可否......
  • 单调栈
    目录单调栈例题单调栈单调的栈，即插入元素时保证栈内元素是有序的。例题P2422良好的感觉贪心，其实对每一个最小值，找到其的左右小于最大范围，但关键在于怎么快速找到这个范围，这里利用了单调栈详见代码：constintmaxm=1e5+5,inf=0x3f3f3f3f,mod=998244353;lln,a[maxm],sum[......
  • day114- 动态sql
    动态SQL解决拼接SQL语句字符串时的问题。if标签if标签可通过test属性的表达式进行判断，若表达式的结果为true，则标签中的内容会执行；反之标签中的内容不会执行<!--List<Emp>getEmpByCondition(Empemp);--><selectid="getEmpByCondition"resultType="com.gu.mybatis.poj......
  • 第二阶段知识点总结【day32-day35】
    第二阶段知识点总结day321.面向过程和面向对象优缺点，使用场景2.如何定义类，写出一个例子，定义类的过程发生了那些事，如何产生对象，产生的对象有何特点3.如何定制对象自己的属性4.属性的查找顺序是怎样的day331.分别写出一个绑定方法，非绑定方法的例子2.如何隐藏属性，写一个例子，......
  • 第二阶段知识点总结解释版【day32-day35】
    知识点总结day321.面向过程和面向对象优缺点，使用场景面向过程和面向对象都是编程的两种不同的范式。面向过程的优点：1.执行速度比面向对象更快。2.简单易懂，且不需要大量的规则或语法。3.它适合在小型程序中使用。面向过程的缺点：1.没有高度的拓展性。2.系统难以......
  • Java基础-Day06
    Java基础-Day06多维数组如何理解二维数组？数组属于引用数据类型数组的元素也可以是引用数据类型一个一维数组A的元素如果还是一个一维数组类型的，则次数组称为二维数组二维数组的属性：int[][]arr3=newint[][]{{1,2,3,4},{4,5,6,7,8},{9,10}};Syste......
  • python基础day35 Mixins机制和元类
    Mixins机制classVehicle:#交通工具passclassFlyMinix():deffly(self):'''飞行功能相应的代码'''print("Iamflying")'''1.主类：就是大部分都是主要的功能2.辅类：就是一些辅助的功能3.辅类的类名也......
  • 每日一练 | 华为认证真题练习Day69
    1、STP协议在以下哪个状态下进行端口角色的选举？A.BlockingB.DisabledC.LearningD.Listening2、RSTPBPDU报文中的Flag字段的总长度为多少bit？A.6B.4C.8D.23、以下哪项不是RSTP可以提高收敛速度的原因？A.边缘端口的引入B.取消了ForwardDelayC.根端口的快速切换D.P/A机制4......
  • day 113- mybatis的查询resultMap
    mybatis中的resultMapresultMap用来处理字段名和属性名不一致的情况，处理映射关系若字段名和实体类中的属性名不一致，则可以通过resultMap设置自定义映射<!--字段名和属性名不一致的情况，处理映射关系：1.为查询的字段设置别名，和属性名保持一致2.当字段符合MySQL......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99