专栏文章

7.31 比赛总结

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

文章操作

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

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

B3667 求区间所有后缀最大值的位置

错误代码如下：

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n,k;
const int maxn=1e6+10;
int a[maxn];
deque<int>q;
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		if(!q.empty()&&q.front()<=i-k+1){
			q.pop_front();
		}
		while(!q.empty()&&a[i]>=a[q.back()]){
			q.pop_back();
		}
		q.push_back(i);
		
		if(i>=k){
			cout<<q.size()<<endl;
		}
	}
	return 0;
}
//错误代码
题目要求：对于全部的测试点，保证 1≤k≤n≤10 6 ，1≤x i ​ <2 64 。

错因

①所以变量开小了 应该开unsigned long long

②此题判断队首约是否越界 要先入队列 进完后判断是否越界

③并且判断条件出错 减号有风险挂 最好用加法

CPP
#define int unsigned long long

for(int i=1;i<=n;i++){
		while(!q.empty()&&a[i]>=a[q.back()]){
			q.pop_back();
		}
		q.push_back(i);
		if(k+q.front()<=i){
			q.pop_front();
		}
		if(i>=k){
			cout<<q.size()<<endl;
		}
	}

正确完整代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long 
int n,k;
const int maxn=1e6+10;
int a[maxn];
deque<int>q;

signed main(){
	cin>>n>>k;
	
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		while(!q.empty()&&a[i]>=a[q.back()]){
			q.pop_back();
		}
		q.push_back(i);
		if(k+q.front()<=i){
			q.pop_front();
		}
		if(i>=k){
			cout<<q.size()<<endl;
		}
	}
	return 0;
}
//正确代码

P3467 [POI 2008] PLA-Postering

错误代码如下

CPP
#include<bits/stdc++.h>
using namespace std;
int n;
const int maxn=1e6+10;
int a[maxn];
stack<int>q;
int ans;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		while(!q.empty()&&a[i]<=a[q.top()]){
			if(a[i]==a[q.top()])ans++;
			q.pop();
		}
		if(!q.empty())ans++;
		q.push(i);
	}

	cout<<ans; 

	return 0;
}
//错误

错因

思路出错

应该cnt初始等于n(最坏情况 每一个高度都不相同)

然后维护一个单调递增的栈 违法后判断是否相等 相等可以连接成一块 即只需要一张报纸 所以总数少一张报纸（cnt--） 最后输出cnt即可

正确代码

CPP
#include<bits/stdc++.h>
using namespace std;
int n;
const int maxn=1e6+10;
int a[maxn];
stack<int>q;
int ans;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		cin>>a[i];
	}
	ans=n;
	for(int i=1;i<=n;i++){
		while(!q.empty()&&a[i]<a[q.top()]){
			q.pop();
		}
		if(!q.empty()&&a[i]==a[q.top()])ans--;
		q.push(i);
	}
	cout<<ans;

	return 0;
}
//正确

P1823 [COI 2007] Patrik 音乐会的等待

错因

①维护单调栈顺序错误 应该维护单调递减的栈

②并且在维护过程中循环内也属于单调递增的效果 所以可以在一个循环内进行 合法结束cnt++

③当两边相等的时候需要a[i].num+=q.top().num;

正确代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int maxn=1e6+10;
struct S{
	int x;
	int num=1;
}a[maxn];
stack<S>q;
int n;
int ans;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].x;
	}
	for(int i=1;i<=n;i++){
		while(!q.empty()&&a[i].x>=q.top().x){
			ans+=q.top().num;
			if(a[i].x==q.top().x)a[i].num+=q.top().num;
			q.pop();
			
		}
		if(!q.empty()){
			ans++;
		}
		q.push(a[i]);
	}

	cout<<ans;
	return 0;
}
//正确

P2564 [SCOI2009] 生日礼物

这道题与上课例题相似

上课专注度需加强

这种类型题目得重新巩固

没理解特别多

正确代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct node
{
int pos,id;
}s[N];
bool cmp(node q,node h)
{
return q.pos<h.pos;
}
int n,k,cnt,tot,num[N],minn=1e9;

map<int,int> ma;
deque<int> q;
int main()
{
	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+1+n,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.empty() && 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;
}

综上所述

我的单调队列和单调栈需要加强

平时上课的最优解要巩固

滑动窗口时判断是否队首越界的代码要加强

并且看题要看数据范围

评论

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

正在加载评论...