第二周 题目练习2（stack综合 单调栈）牛客 14326. 14666. 15029
栈版子
Rails
栈模拟模板题，核心思路是模拟真实的入栈、出栈过程
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES cout<<"YES"<<endl; #define NO cout<<"NO"<<endl; using namespace std; ll n; int main() { IOS while(cin>>n&&n!=0) { ll x; while(cin>>x) { if(x==0)break; vector<ll>goal; goal.push_back(x); for(ll i=1;i<n;i++) { cin>>x; goal.push_back(x); } stack<ll>st; ll num=1; bool ok=true; for(ll a:goal) { while(st.empty()||st.top()!=a) { st.push(num); num++; if(num>n+1) { ok=false; break; } } if(!ok)break; st.pop(); } if(ok)cout<<"Yes"<<endl; else cout<<"No"<<endl; } cout<<endl; } // cout<<fixed<<setprecision(x)<< ; return 0; }最优屏障
给定一排山峰，两座山可以相互看见当且仅当它们中间没有更高或等高的山。在某两座山之间放置屏障，会切断所有跨越该位置的可视山峰对。
要求：找到切断可视对最多的屏障位置；若多个位置答案相同，输出编号最小的位置。
解题过程
1.核心思想：贡献法 + 单调栈 + 差分
直接暴力枚举所有山峰对会超时。
因此枚举每一对可见山峰，给对应的屏障区间统计贡献。
对于任意一对可见山峰 (l, r)：
屏障放在 [l, r-1] 任意位置，都能切断这一对。
等价于：对区间 [l, r-1]整体 +1。
2.差分优化区间修改
一维差分可以 O(1) 完成区间加：
区间 [L,R] +1：d[L]++, d[R+1]–
本题代入：L=l，R=r-1，得到固定写法：
d[l]++, d[r]–
3.单调栈找所有可见山峰对
维护一个单调递减栈存储山峰下标：
遍历当前山峰 r，弹出所有左侧更矮的山 l：两者可见，统计贡献
栈不为空时，剩余栈顶高山也与 r 可见，统计贡献但不弹出（后续继续使用）
当前山峰入栈，维持单调性
4.前缀和求答案
对差分数组做前缀和，得到每个屏障位置切断的总对数，遍历维护最大值、最小下标即可
注：题目屏障下标从第 1、2 座山之间开始，代码统计下标偏移，所以最终输出需要 ansx+1
代码实现
#include<bits/stdc++.h> #define ll long long #define endl '\n' // #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES cout<<"YES"<<endl; #define NO cout<<"NO"<<endl; using namespace std; ll t; ll n; ll ansx,now,maxless; int main() { scanf("%lld",&t); for(ll cas=1;cas<=t;cas++) { scanf("%lld",&n); vector<ll>h(n+2); vector<ll>d(n+2,0); for(ll i=1;i<=n;i++) { scanf("%lld",&h[i]); } stack<ll>st; for(ll r=1;r<=n;r++) { while(!st.empty()&&h[st.top()]<h[r]) { ll l=st.top(); st.pop(); //可视对(l,r) ,等价于[l,r-1]+1; d[l]+=1; d[r]-=1; } if(!st.empty()) { ll l=st.top(); d[l]++; d[r]--; } st.push(r); } now=0; maxless=-1; ansx=1; for(ll i=1;i<=n;i++) { now+=d[i]; if(now>maxless||(now==maxless&&i<ansx)) { maxless=now; ansx=i; } } printf("Case #%lld: %lld %lld\n",cas,ansx+1,maxless); } // cout<<fixed<<setprecision(x)<< ; return 0; }吐泡泡
解题过程
栈实时 化简：遍历字符串，逐个字符入栈；
每入栈一个字符，循环检查栈顶两个元素，满足合并 / 抵消规则则立即处理，直至无法匹配。
结果顺序处理：栈结构先进后出，取出栈内字符会得到逆序字符串，最后反转字符串得到正确顺序输出；
代码实现
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES cout<<"YES"<<endl; #define NO cout<<"NO"<<endl; using namespace std; ll t; string s; string ans; int main() { IOS cin>>t; while(t--) { cin>>s; ll l=s.size(); stack<char>st; for(char c:s) { st.push(c); while(st.size()>=2) { char top1=st.top(); st.pop(); char top2=st.top(); if(top1=='o'&&top2=='o') { st.pop(); st.push('O'); } else if(top1=='O'&&top2=='O') { st.pop(); } else { st.push(top1); break; } } } ans=""; while(!st.empty()) { ans+=st.top(); st.pop(); } reverse(ans.begin(),ans.end()); cout<<ans<<endl; } // cout<<fixed<<setprecision(x)<< ; return 0; }