专栏文章

"7-31晚 单调栈和单调队列"总结

rren_gao_zu
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miol9u8e
此快照首次捕获于
2025/12/02 21:03
3 个月前
此快照最后确认于
2025/12/02 21:03
3 个月前
查看原文

考试情况

题目模拟赛分数
T1100100
T2100100
T300
T499
T53434
T600
T700
T82828
T900
sum271（寄271（寄

错题总结（不含T8、T9）

T3:

死因：不开unsigned long long 见祖宗

错误片段：
CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
const int N=1e6+5;
using namespace std;
正确：
CPP
#include<bits/stdc++.h>
#define int unsigned long long
#define endl '\n'
const int N=1e6+5;
using namespace std;
为什么别人不开unsigned long long得25分，我不开unsigned long long得0分!!!

正确代码：

单调队列模版,唯一的就是要开unsigned long long
CPP
#include<bits/stdc++.h>
#define int unsigned long long
#define endl '\n'
const int N=1e6+5;
using namespace std;
int n,m,a[1000005],mi[1000005];
deque<int>q;
void solve();
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	solve();
	return 0;
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<m;i++){
		while(q.size()&&a[q.back()]<=a[i])q.pop_back();
		q.push_back(i);
	}
	for(int i=m;i<=n;i++){
		while(q.size()&&a[q.back()]<=a[i]){
			q.pop_back();
		}
		if(i>m){
			if(q.size()&&q.front()==i-m)q.pop_front();
		}
		q.push_back(i);
		cout<<q.size()<<endl;


	}
}

T4:

死因：只正着跑了一遍，但还要清空再倒着跑一遍

错误片段：
CPP
	for(int i=1;i<=n;i++){
		while(st.size()&&a[st.top()]>=a[i])ans+=i-st.top()+1,st.pop();
		if(st.size())ans+=st.top()-i+1;
		st.push(i);
	}
    ...
    ...
	cout<<ans*2;
正确：
CPP
	for(int i=n;i>=1;i--){
		while(st.size()&&a[i]>=a[st.top()])st.pop();
		if(st.size())ans+=st.top()-i+1;
		st.push(i);
	}
	while(st.size())st.pop();
	for(int i=1;i<=n;i++){
		while(st.size()&&a[i]>a[st.top()])st.pop();
		if(st.size())ans+=i-st.top()+1;
		st.push(i);
	}
	cout<<ans;

正确代码：

就是单调栈，但正向跑完一遍还要清空栈并反向跑一遍(先正先反都可以)
还要注意：ans加的距离不要搞错了，加错了ans加的有可能是负数。(不能加abs)
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1000005],ans;
stack<int>st;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=n;i>=1;i--){
		while(st.size()&&a[i]>=a[st.top()])st.pop();
		if(st.size())ans+=st.top()-i+1;
		st.push(i);
	}
	while(st.size())st.pop();
	for(int i=1;i<=n;i++){
		while(st.size()&&a[i]>a[st.top()])st.pop();
		if(st.size())ans+=i-st.top()+1;
		st.push(i);
	}
	cout<<ans;
	return 0;
}

T5：

死因：理解错误

错误片段：
CPP
for(int i=1;i<=n;i++){
		while(st1.size()&&a[st1.top()]>a[i])st1.pop(),ans++;
		if(st1.size()&&a[i]!=a[st1.top()])st1.push(i);
		if(i==1)st1.push(i);
	}
我当时是怎么想的，怎么会写出这种东西
正确：
CPP
for(int i=1;i<=n;i++){
		while(st1.size()&&a[st1.top()]>a[i])st1.pop(),ans++;
		if(st1.size()&&a[i]==a[st1.top()])continue;
		st1.push(i);
	}

正确代码

首先，宽度没有任何作用，如果想要海报数最少，至少这堵墙可以用一张海报贴完，不可能一堵墙用两三张海报，所以宽度没用
然后维护一个单调递增的栈，如果遇到栈顶小于a[i]，就将栈顶出栈，并ans++。如果栈顶和a[i]高度相等，这两个可以合并成一堵墙，宽度为a[i]和st.top()的宽度之和，但宽度没用，所以实际上如果a[st.top()]==a[i]a[st.top()]==a[i],a[i]是不用进栈的。
最后直接输出ans+st.size()ans+st.size()即可
CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
const int N=1e6+5;
using namespace std;
int n,a[N],ans;
stack<int>st1;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int ffff;
		cin>>ffff>>a[i];
	}
	for(int i=1;i<=n;i++){
		while(st1.size()&&a[st1.top()]>a[i])st1.pop(),ans++;
		if(st1.size()&&a[i]==a[st1.top()])continue;
		st1.push(i);
	}
	cout<<ans+st1.size();
	return 0;
}

T6:

死因：can't do it(不会做)

错误片段：
不要看了，随机数(果然不能相信随机数)

正确代码

首先把所有数据存到一个结构体数组s[]里，并按位置从小到大排序。
然后遍历s数组，用一个num数组存每一种珍珠在队列里的数量，cnt存在队列里的颜色数量。每次将进队的珍珠的颜色加1，如果这个珍珠颜色原来没有，cnt++。若颜色数量大于等于种类数，即cnt>=kcnt>=k，就把队首出队，如果出队的这个珍珠的颜色数量变成0了，cnt--。
minn代表彩带的最短长度，彩带长度为队尾位置-队首位置。若果minn大于彩带长度，更新minn。
最后输出minn。
CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
const int N=1e6+5;
using namespace std;
int n,k,tot,num[N],minn=1e18,cnt;
struct node{
	int pos,id;
}s[N];
bool cmp(node x,node y){
	return x.pos<y.pos;
}
deque<int>q;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		int t;
		cin>>t;
		while(t--){
			int x;
			cin>>x;
			tot++;
			s[tot].pos=x;
			s[tot].id=i;
		}
	}
	sort(s+1,s+n+1,cmp);
	for(int i=1;i<=n;i++){
		q.push_back(i);
		int id=s[i].id;
		if(num[id]==0)cnt++;
		num[id]++;
		while(q.size()&&cnt>=k){
			int j=q.front();
			q.pop_front();
			int id=s[j].id;
			num[id]--;
			if(num[id]==0){
				cnt--;
				minn=min(minn,s[i].pos-s[j].pos);
			}
		}
		
	}cout<<minn;
	return 0;
}

T7:

死因：似乎忘记怎么写了

错误片段：
几乎全错

正确代码：

这题有一个问题：任意两个人之间的人可以等于这两个人的较小值，导致之前的代码无法通过。
我们可以定义一个结构体node，用来存储高度和数量。输入数组s和栈都是node类型。
遍历数组s，如果s[i].h大于等于栈顶的高度，sum加上栈顶的数量，如果s[i].h等于栈顶的高度s[i]的数量加上栈顶的数量，然后把栈顶出栈。如果栈里面还有元素，sum++。最后将s[i]压入栈。
最后输出sum。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[10000005];
struct node{
	int h,num;
}s[100005];
stack<node>st;
int n;
int sum;
signed main()
{

	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i].h;
		s[i].num=1;
	}

	for(int i=1;i<=n;i++)
    {
		while(st.size()&&s[i].h>=st.top().h)
        {
            sum+=st.top().num;
            if(s[i].h==st.top().h){
            	s[i].num+=st.top().num;
			}
            st.pop();

        }
        if(st.size()){
        	sum++;
		}
		st.push(s[i]);
	}
	cout<<sum;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...