noi-2026年3月17号作业

题目B3614 【模板】栈网址https://www.luogu.com.cn/problem/B3614思路我们使用一个一维的数组来模拟栈栈只有从顶部才能加入数据知识点栈代码:#includebits/stdc.h #define ull unsigned long long using namespace std; const int maxn1e6100; ull a[maxn],cnt; void solve() { int n; cinn; cnt0; while(n--) { string op; cinop; if(oppush) { ull x; cinx; a[cnt]x; }else if(oppop) { if(cnt0) coutEmpty\n; else cnt--; }else if(opquery) { if(cnt0) coutAnguei!\n; else couta[cnt]\n; }else if(opsize) { coutcnt\n; } } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T; cinT; while(T--) solve(); return 0; }题目B3616 【模板】队列网址https://www.luogu.com.cn/problem/B3616思路我们使用一个一维的数组来模拟队列L代表队首R代表队尾。知识点队列代码:#includebits/stdc.h #define ll long long #define fi first #define se second #define pii pairint,int #define pb push_back using namespace std; const int maxn2e6100; ll n,m,a[maxn]; ll ans,sum; int L1000000,R1000000-1; void solve() { int q; cinq; while(q--) { int op; cinop; if(op1) { ll x; cinx; a[R]x; }else if(op2) { if(LR) coutERR_CANNOT_POP\n; else L; }else if(op3) { if(LR) coutERR_CANNOT_QUERY\n; else couta[L]\n; }else if(op4) { coutR-L1\n; } } } int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int _; _1; // cin_; while(_--) solve(); return 0; }题目P1739 表达式括号匹配网址https://www.luogu.com.cn/problem/P1739思路知识点栈代码:#includebits/stdc.h #define ll long long #define fi first #define se second #define pii pairint,int #define pb push_back using namespace std; const int maxn2e6100; ll n,m,a[maxn]; ll ans,sum; string str; void solve() { cinstr; int lenstr.length(); int cnt0; for(int i0;ilen;i) { if(str[i]() cnt; else if(str[i])) cnt--; if(cnt0) { coutNO\n; return; } } if(cnt!0) { coutNO\n; return; } coutYES\n; } int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int _; _1; // cin_; while(_--) solve(); return 0; }题目P1449 后缀表达式网址https://www.luogu.com.cn/problem/P1449思路我们按照题目的意思去模拟就行知识点后缀表达式模拟代码:#includebits/stdc.h #define ull unsigned long long #define ll long long #define pll pairll,ll #define fi first #define se second #define db double #define eb emplace_back #define pb push_back using namespace std; const int maxn1e6100; const ll mode21e97; int vis[maxn]; string str; ll a[maxn]; ll n,m; void solve() { cinstr; int lenstr.length(); stackllst; int j; for(int i0;ilen;ij) { ji1; if(str[i]) break; if(str[i]/) { ll v1st.top(); st.pop(); ll v2st.top(); st.pop(); st.push(v2/v1); }else if(str[i]) { ll v1st.top(); st.pop(); ll v2st.top(); st.pop(); st.push(v2v1); }else if(str[i]-) { ll v1st.top(); st.pop(); ll v2st.top(); st.pop(); st.push(v2-v1); }else if(str[i]*) { ll v1st.top(); st.pop(); ll v2st.top(); st.pop(); st.push(v2*v1); }else{ ll vstr[i]-0; while(jlenstr[j]0str[j]9) { vv*10(str[j]-0); j; } j; st.push(v); } } coutst.top(); } int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int T1; // cinT; while(T--) solve(); return 0; }题目P4387 【深基15.习9】验证栈序列网址https://www.luogu.com.cn/problem/P4387思路我们按照输入的顺序一直入栈入栈的同时判断是否可以出栈如果最后还有元素的话这么说明一定是NO知识点模拟代码:#includebits/stdc.h #define ull unsigned long long #define ll long long #define pll pairll,ll #define fi first #define se second #define db double #define eb emplace_back #define pb push_back using namespace std; const int maxn1e6100; const ll mode21e97; int vis[maxn]; string str; ll a[maxn]; ll n,m; ll b[maxn]; void solve() { cinn; for(int i1;in;i) cina[i]; for(int i1;in;i) cinb[i]; stackllst; int k1; for(int i1;in;i) { st.push(a[i]); while(knst.size()st.top()b[k]) { st.pop(); k; } } if(st.size()) coutNo\n; else coutYes\n; } int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int T1; cinT; while(T--) solve(); return 0; }题目P1165 日志分析网址https://www.luogu.com.cn/problem/P1165思路我们每次把还存在的货物的最大值放进去知识点模拟思维代码:#includebits/stdc.h #define ull unsigned long long #define ll long long #define pll pairll,ll #define fi first #define se second #define db double #define eb emplace_back #define pb push_back using namespace std; const int maxn1e6100; const ll mode21e97; int vis[maxn]; string str; ll a[maxn]; ll n,m; void solve() { cinn; ll mx0; stackllst; while(n--) { int op; cinop; if(op0) { ll x; cinx; if(st.size()) st.push(max(x,st.top())); else st.push(x); }else if(op1) { if(st.size()) st.pop(); }else if(op2) { if(st.size()) coutst.top()\n; else cout0\n; } } } int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int T1; // cinT; while(T--) solve(); return 0; }题目P1886 【模板】单调队列 / 滑动窗口网址https://www.luogu.com.cn/problem/P1886思路单调队列模板题知识点单调队列代码:#includebits/stdc.h #define ull unsigned long long #define ll long long #define pll pairll,ll #define fi first #define se second #define db double #define eb emplace_back #define pb push_back using namespace std; const int maxn1e6100; const ll mode21e97; int vis[maxn]; string str; ll a[maxn]; ll n,m,k; struct node_mx{ ll val,pos; bool operator (const node_mx nd)const { return valnd.val; } }; struct node_mn{ ll val,pos; bool operator (const node_mn nd)const { return valnd.val; } }; void solve() { cinnk; for(int i1;in;i) { cina[i]; } priority_queuenode_mxqmx; priority_queuenode_mnqmn; vectorllansmn,ansmx; for(int i1;in;i) { if(ik) { qmx.push({a[i],i}); qmn.push({a[i],i}); continue; } qmx.push({a[i],i}); qmn.push({a[i],i}); while(qmx.size()qmx.top().posi-k) qmx.pop(); while(qmn.size()qmn.top().posi-k) qmn.pop(); ansmn.pb(qmn.top().val); ansmx.pb(qmx.top().val); } for(auto it:ansmn) coutit ; cout\n; for(auto it:ansmx) coutit ; } int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int T1; // cinT; while(T--) solve(); return 0; }题目P5788 【模板】单调栈网址https://www.luogu.com.cn/problem/P5788思路单调栈模板题知识点单调栈代码:#includebits/stdc.h #define ull unsigned long long #define ll long long #define pll pairll,ll #define fi first #define se second #define db double #define eb emplace_back #define pb push_back using namespace std; const int maxn3e6100; const ll mode21e97; int vis[maxn]; string str; ll a[maxn]; ll n,m; ll b[maxn]; void solve() { cinn; for(int i1;in;i) cina[i]; stackintst; for(int in;i1;i--) { while(st.size()a[st.top()]a[i]) st.pop(); if(st.size()) b[i]st.top(); else b[i]0; st.push(i); } for(int i1;in;i) coutb[i] ; } int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int T1; // cinT; while(T--) solve(); return 0; }题目P1440 求m区间内的最小值网址https://www.luogu.com.cn/problem/P1440思路单调栈模板题知识点单调栈代码:#includebits/stdc.h #define ull unsigned long long #define ll long long #define pll pairll,ll #define fi first #define se second #define db double #define eb emplace_back #define pb push_back using namespace std; const int maxn2e6100; const ll mode21e97; int vis[maxn]; string str; ll a[maxn]; ll n,m; struct node{ ll val,pos; bool operator(const nodend)const { return valnd.val; } }; void solve() { cinnm; for(int i1;in;i) cina[i]; priority_queuenodeq; for(int i1;in;i) { if(q.size()0) { cout0\n; q.push({a[i],i}); continue; } while(q.size()q.top().posi-m) q.pop(); coutq.top().val\n; q.push({a[i],i}); } } int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int T1; // cinT; while(T--) solve(); return 0; }题目P1311 [NOIP 2011 提高组] 选择客栈网址https://www.luogu.com.cn/problem/P1311思路我们对每一种格调记录一下有多少个店它右边有店的最低消费是小于等于p的。知识点思维题代码:#includebits/stdc.h #define ull unsigned long long #define ll long long #define pll pairll,ll #define fi first #define se second #define db double #define eb emplace_back #define pb push_back using namespace std; const int maxn2e5100; const ll mode21e97; int vis[maxn]; string str; ll a[maxn],b[maxn],cnt[100]; ll n,m,k,p; void solve() { cinnkp; ll ans0,last0; for(int i1;in;i) { cina[i]b[i]; } for(int i1;in;i) { if(b[i]p) { for(int jlast1;ji;j) cnt[a[j]]; lasti; anscnt[a[i]]-1; }else{ anscnt[a[i]]; } } coutans; } int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int T1; // cinT; while(T--) solve(); return 0; }