🚀欢迎来到本文🚀
🍉个人简介：陈童学哦，目前正在学习C/C++、Java、算法等方向，一个正在慢慢前行的普通人。
🏀系列专栏：陈童学的日记
💡其他专栏：C++STL，感兴趣小伙伴可以了解一下哦
🎁希望各位→点赞👍 + 收藏⭐️ + 留言📝
⛱️万物随心起，心动则万物动🤺
Day2集训
- 前言
- A - 表达式的转换
- 解题思路
- 示例代码
- B - Look Up S
- 解题思路
- 示例代码
- C - ICPC Balloons
- 解题思路
- 示例代码
- D - Rudolph and Cut the Rope
- 解题思路
- 示例代码
- E - 后缀表达式
- 解题思路
- 示例代码
- F - Pashmak and Flowers
- 解题思路
- 示例代码
- 总结
前言
因参加了我校的ACM暑期集训为之后的xcpc等赛事做准备，所以就有了此文哈哈。本文主要复盘做题的过程以及一些感悟，便于复习巩固。辣么现在废话也不多说啦，直接往下看吧哈哈。
A - 表达式的转换
来源：洛谷P1175 表达式的转换
解题思路
本题是道用栈实现后缀表达式的模拟题，但是实现过程还是有点复杂的，好家伙第一题就给我上难度是吧。
主要的就是注意下（）以及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 - 后缀表达式
来源：洛谷P1449 后缀表达式
解题思路
本题又是道后缀表达式的题，我们用数组来模拟栈。
示例代码
#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的题主要考察的也是一些基础的算法，有些稍复杂。
算法：单调栈、线性结构、模拟、暴力
感悟：这些算法算也是较基础的，但还需多加练习达到更快解题
总结：每个算法都有其巧妙处，一些模拟题也是较为繁琐很是考察逻辑思维的
