第二周 题目练习2（stack综合 单调栈）牛客 14326. 14666. 15029

栈版子Rails栈模拟模板题核心思路是模拟真实的入栈、出栈过程#includebits/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 coutYESendl; #define NO coutNOendl; using namespace std; ll n; int main() { IOS while(cinnn!0) { ll x; while(cinx) { if(x0)break; vectorllgoal; goal.push_back(x); for(ll i1;in;i) { cinx; goal.push_back(x); } stackllst; ll num1; bool oktrue; for(ll a:goal) { while(st.empty()||st.top()!a) { st.push(num); num; if(numn1) { okfalse; break; } } if(!ok)break; st.pop(); } if(ok)coutYesendl; else coutNoendl; } coutendl; } // coutfixedsetprecision(x) ; return 0; }最优屏障给定一排山峰两座山可以相互看见当且仅当它们中间没有更高或等高的山。在某两座山之间放置屏障会切断所有跨越该位置的可视山峰对。要求找到切断可视对最多的屏障位置若多个位置答案相同输出编号最小的位置。解题过程1.核心思想贡献法 单调栈 差分直接暴力枚举所有山峰对会超时。因此枚举每一对可见山峰给对应的屏障区间统计贡献。对于任意一对可见山峰 (l, r)屏障放在 [l, r-1] 任意位置都能切断这一对。等价于对区间 [l, r-1]整体 1。2.差分优化区间修改一维差分可以 O(1) 完成区间加区间 [L,R] 1d[L], d[R1]–本题代入LlRr-1得到固定写法d[l], d[r]–3.单调栈找所有可见山峰对维护一个单调递减栈存储山峰下标遍历当前山峰 r弹出所有左侧更矮的山 l两者可见统计贡献栈不为空时剩余栈顶高山也与 r 可见统计贡献但不弹出后续继续使用当前山峰入栈维持单调性4.前缀和求答案对差分数组做前缀和得到每个屏障位置切断的总对数遍历维护最大值、最小下标即可注题目屏障下标从第 1、2 座山之间开始代码统计下标偏移所以最终输出需要 ansx1代码实现#includebits/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 coutYESendl; #define NO coutNOendl; using namespace std; ll t; ll n; ll ansx,now,maxless; int main() { scanf(%lld,t); for(ll cas1;cast;cas) { scanf(%lld,n); vectorllh(n2); vectorlld(n2,0); for(ll i1;in;i) { scanf(%lld,h[i]); } stackllst; for(ll r1;rn;r) { while(!st.empty()h[st.top()]h[r]) { ll lst.top(); st.pop(); //可视对(l,r) ,等价于[l,r-1]1; d[l]1; d[r]-1; } if(!st.empty()) { ll lst.top(); d[l]; d[r]--; } st.push(r); } now0; maxless-1; ansx1; for(ll i1;in;i) { nowd[i]; if(nowmaxless||(nowmaxlessiansx)) { maxlessnow; ansxi; } } printf(Case #%lld: %lld %lld\n,cas,ansx1,maxless); } // coutfixedsetprecision(x) ; return 0; }吐泡泡解题过程栈实时 化简遍历字符串逐个字符入栈每入栈一个字符循环检查栈顶两个元素满足合并 / 抵消规则则立即处理直至无法匹配。结果顺序处理栈结构先进后出取出栈内字符会得到逆序字符串最后反转字符串得到正确顺序输出代码实现#includebits/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 coutYESendl; #define NO coutNOendl; using namespace std; ll t; string s; string ans; int main() { IOS cint; while(t--) { cins; ll ls.size(); stackcharst; for(char c:s) { st.push(c); while(st.size()2) { char top1st.top(); st.pop(); char top2st.top(); if(top1otop2o) { st.pop(); st.push(O); } else if(top1Otop2O) { st.pop(); } else { st.push(top1); break; } } } ans; while(!st.empty()) { ansst.top(); st.pop(); } reverse(ans.begin(),ans.end()); coutansendl; } // coutfixedsetprecision(x) ; return 0; }