前言
因参加了我校的ACM暑期集训为之后的xcpc等赛事做准备，所以就有了此文哈哈。本文主要复盘做题的过程以及一些感悟，便于复习巩固。辣么现在废话也不多说啦，直接往下看吧哈哈。
A - 表达式的转换
解题思路
本题是道用栈实现后缀表达式的模拟题，但是实现过程还是有点复杂的，好家伙第一题就给我上难度是吧。
主要的就是注意下（）以及2^ 2 ^ 3的是从后往前计算的。我自己刚开始是没做出来的，我看了题解的哈哈。
示例代码
#include <bits/stdc++.h> using namespace std; stack<char> s1,s2; stack<int> s3,s4; int judge1(char c) { switch(c) { case '+':return 1; case '-':return 1; case '*':return 2; case '/':return 2; case '^':return 3; case '(':return 0; case ')':return 0; default:return -1; } } int judge2(int x,int y,char t) { switch(t) { case '+':return x+y; case '-':return x-y; case '*':return x*y; case '/':return x/y; case '^':return pow(x,y); default:return -0x3f3f3f3f; } } void change(string s) { int len=s.size(); for(int i=0;i<len;i++) { if(isdigit(s[i])) s1.push(s[i]); else if(s[i]=='(') s2.push(s[i]); else if(s[i]==')') { char t=s2.top(); while(t!='(') { s2.pop(); s1.push(t); t=s2.top(); } s2.pop(); } else if(judge1(s[i])>=1&&judge1(s[i])<=3) { if(!s2.empty()) { char t=s2.top(); while(!s2.empty()&&judge1(s[i])<=judge1(t)) { if(judge1(s[i])==judge1(t)&&s[i]=='^') break; s2.pop(); s1.push(t); if(!s2.empty()) t=s2.top(); } } s2.push(s[i]); } } while(!s2.empty()) { char t=s2.top(); s2.pop(); s1.push(t); } while(!s1.empty()) { char t=s1.top(); s1.pop(); s2.push(t); } while(!s2.empty()) { char t=s2.top(); cout<<t<<' '; s2.pop(); s1.push(t); } cout<<endl; } void calc() { while(!s1.empty()) { char t=s1.top(); s1.pop(); s2.push(t); } while(!s2.empty()) { char t=s2.top(); s2.pop(); if(isdigit(t)) s3.push(t-'0'); else { int x=s3.top(); s3.pop(); int y=s3.top(); s3.pop(); s3.push(judge2(y,x,t));//传参数时要把x和y反过来 while(!s3.empty()) { int t=s3.top(); s3.pop(); s4.push(t); } while(!s4.empty()) { int t=s4.top(); cout<<t<<' '; s4.pop(); s3.push(t); } while(!s2.empty()) { char t=s2.top(); cout<<t<<' '; s2.pop(); s1.push(t); } while(!s1.empty()) { char t=s1.top(); s1.pop(); s2.push(t); } cout<<endl; } } } int main() { string s; cin>>s; change(s); calc(); return 0; }
B - Look Up S
来源：洛谷P2947 [USACO09MAR] Look Up S
解题思路
本题可以用单调栈的思想解决，我这里用的是一种倒序递归的方法来优化时间的（学一位大佬的哈哈）。
示例代码
#include<iostream> #include<cstdio> using namespace std; const int N=100010; int n,t=1; int a[N],b[N]; int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=n-1;i>=1;i--){ int j=i+1; while(a[i]>=a[j]&&a[j]>0) j=b[j]; b[i]=j; } for(int i=1;i<=n;i++) cout<<b[i]<<endl; }
C - ICPC Balloons
来源：t CodeForces-1703B. ICPC Balloons
解题思路
本题暴力模拟一下就OK啦
示例代码
#include<bits/stdc++.h> using namespace std; int t,n,ans=0; char c; int main(){ cin>>t; while(t--){ int s[100005]={0}; cin>>n; for(int i=1;i<=n;i++){ cin>>c; if(s[c]==0){ s[c]=1; ans+=2; } else ans+=1; } cout<<ans<<endl; ans=0; } }
D - Rudolph and Cut the Rope
来源：CodeForces - 1846A. Rudolph and Cut the Rope
解题思路
本题其实是道简单的模拟题，主要是能理解题意，题目的意思是所有的钉子都绑了不同的绳子一段，而这些不同绳子的另一端都绑了同一颗糖果，而想要这颗糖果落地的话，只需剪掉比绳子长度比钉子高度小的即可。
示例代码
#include <bits/stdc++.h> using namespace std; int t; int n,a,b,ans; int main() { cin>>t; while(t--) { cin>>n; for(int i=1;i<=n;i++) { cin>>a>> b; if(a>b) ans++; } cout < ans<< endl; ans=0; } }
E - 后缀表达式
解题思路
本题又是道后缀表达式的题，我们用数组来模拟栈。
示例代码
#include<iostream> #include<cstdio> using namespace std; long long s[1005]; long long i=0,a=0; char c; int main(){ while((c=getchar())!='@'){ if(c>='0'&&c<='9'){ a*=10; a+=c-'0'; }else if(c=='.'){ s[++i]=a; a=0; }else if(c=='+'){ s[i-1]=s[i-1]+s[i]; s[i]=0; i--; }else if(c=='-'){ s[i-1]=s[i-1]-s[i]; s[i]=0; i--; }else if(c=='*'){ s[i-1]=s[i-1]*s[i]; s[i]=0; i--; }else if(c=='/'){ s[i-1]=s[i-1]/s[i]; s[i]=0; i--; } } cout<<s[1]<<endl; }
F - Pashmak and Flowers
来源：CodeForces - 459B. Pashmak and Flowers
解题思路
本题模拟走一遍便输入边找最大值、最大值个数、最小值、最小值个数就好了，注意特殊情况最大值最小值相同时的处理就好啦。
示例代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f,N=500005; ll n,x,y,maxn=-1,minn=INF,a[N]; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; if(a[i]==maxn) x++; if(a[i]>maxn){ maxn=a[i]; x=1; } if(a[i]==minn) y++; if(a[i]<minn){ minn=a[i]; y=1; } } if(maxn==minn) cout<<0<<" "<<n*(n-1)/2<<endl; //相同时双方是一样的所以需除以2 else cout<<maxn-minn<<" "<<x*y<<endl; //正常情况正常输出 }
总结
Day2的题主要考察的也是一些基础的算法，有些稍复杂。
算法：单调栈、线性结构、模拟、暴力
感悟：这些算法算也是较基础的，但还需多加练习达到更快解题
总结：每个算法都有其巧妙处，一些模拟题也是较为繁琐很是考察逻辑思维的
