【ACM】—蓝桥杯大一暑期集训Day2

男娘i 2024-04-17 10:11 105阅读 0赞

> ?欢迎来到本文?  
> ?个人简介：[陈童学哦][Link 1]，目前学习C/C++、算法、Python、Java等方向，一个正在慢慢前行的普通人。  
> ?系列专栏：[陈童学的日记][Link 2]  
> ?其他专栏：[C++STL][C_STL]，感兴趣的小伙伴可以看看。  
> ?希望各位→点赞? + 收藏⭐️ + 留言?  
> ⛱️学习应使你快乐！望与诸君共勉！?♂️

![在这里插入图片描述][dcdcc7d1acc2445d81614edee48e34e9.png]

#### Day2集训 ####

*  前言
 *  A - 表达式的转换
 *   *  解题思路
     *  示例代码
 *  B - Look Up S
 *   *  解题思路
     *  示例代码
 *  C - ICPC Balloons
 *   *  解题思路
     *  示例代码
 *  D - Rudolph and Cut the Rope
 *   *  解题思路
     *  示例代码
 *  E - 后缀表达式
 *   *  解题思路
     *  示例代码
 *  F - Pashmak and Flowers
 *   *  解题思路
     *  示例代码
 *  总结

## 前言 ##

> 因参加了我校的ACM暑期集训为之后的xcpc等赛事做准备，所以就有了此文哈哈。本文主要复盘做题的过程以及一些感悟，便于复习巩固。辣么现在废话也不多说啦，直接往下看吧哈哈。

## A - 表达式的转换 ##

**来源：**[洛谷P1175 表达式的转换][P1175]  
![在这里插入图片描述][e1d71e931a8f44fa8b1d8da07b8ec774.png]  
![在这里插入图片描述][ebd93e169f2f42fa8900ae66bc05aa1c.png]

### 解题思路 ###

本题是道用栈实现`后缀表达式`的`模拟`题，但是实现过程还是有点复杂的，好家伙第一题就给我上难度是吧。  
主要的就是注意下（）以及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][P2947 _USACO09MAR_ Look Up S]  
![在这里插入图片描述][cc21a0e070f343df8c2a898bffdeb468.png]  
![在这里插入图片描述][22904aaaebe24b1a98dca2d8f3b148cc.png]

### 解题思路 ###

本题可以用`单调栈`的思想解决，我这里用的是一种倒序递归的方法来优化时间的（学一位大佬的哈哈）。

### 示例代码 ###

#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][]  
![在这里插入图片描述][7f11fd3d2dea409fbaafef4f5e49b612.png]  
![在这里插入图片描述][4f4538f1c657498fbd93c4a548df2990.png]  
![在这里插入图片描述][40b0112acba74a49b6d703d2580a9a00.png]

### 解题思路 ###

本题暴力模拟一下就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][]

![在这里插入图片描述][5520342c6a82413c84200049ee7699ef.png]  
![在这里插入图片描述][f0ab58db1c1542b196d58fea1aaf11ff.png]

### 解题思路 ###

本题其实是道简单的模拟题，主要是能理解题意，题目的意思是所有的钉子都绑了不同的绳子一段，而这些不同绳子的另一端都绑了同一颗糖果，而想要这颗糖果落地的话，只需剪掉比绳子长度比钉子高度小的即可。

### 示例代码 ###

#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 后缀表达式][P1449]  
![在这里插入图片描述][fdad3772f1744dfcb8b2e689022987ee.png]  
![在这里插入图片描述][6a05f5e0844141d6bfb0569488b7d370.png]

### 解题思路 ###

本题又是道后缀表达式的题，我们用数组来模拟栈。

### 示例代码 ###

#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][]  
![在这里插入图片描述][c66bbe7835164b228211e46b264b0444.png]

![在这里插入图片描述][b6166eaaa84a41cab8d3e6bc1cb20e91.png]

![在这里插入图片描述][d3a27e64a43441ce9ef796e34bc4a692.png]

### 解题思路 ###

本题模拟走一遍便输入边找最大值、最大值个数、最小值、最小值个数就好了，注意特殊情况最大值最小值相同时的处理就好啦。

### 示例代码 ###

#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的题主要考察的也是一些基础的算法，有些稍复杂。  
算法：`单调栈、线性结构、模拟、暴力`  
感悟：这些算法算也是较基础的，但还需多加练习达到更快解题  
总结：每个算法都有其巧妙处，一些模拟题也是较为繁琐很是考察逻辑思维的

[Link 1]: https://blog.csdn.net/H1727548?type=blog
[Link 2]: https://blog.csdn.net/h1727548/category_12342877.html?spm=1001.2014.3001.5482
[C_STL]: https://blog.csdn.net/h1727548/category_12319887.html?spm=1001.2014.3001.5482
[dcdcc7d1acc2445d81614edee48e34e9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/c22752b8f005451e8dd8a60c04d2dc6f.png
[P1175]: https://www.luogu.com.cn/problem/P1175
[e1d71e931a8f44fa8b1d8da07b8ec774.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/4cca423afb364ae880b7270e50ea0b8e.png
[ebd93e169f2f42fa8900ae66bc05aa1c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/48e0a922a2544e58bb33cf514a00444e.png
[P2947 _USACO09MAR_ Look Up S]: https://www.luogu.com.cn/problem/P2947
[cc21a0e070f343df8c2a898bffdeb468.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/c8d4d8620a674d1891ed60f4732c4b7e.png
[22904aaaebe24b1a98dca2d8f3b148cc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/3b2367c7f240449f8a85ecf22ef4136c.png
[t CodeForces-1703B. ICPC Balloons]: https://codeforces.com/problemset/problem/1703/B
[7f11fd3d2dea409fbaafef4f5e49b612.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/17f7c83a7f014e7da5d49996ff76b04c.png
[4f4538f1c657498fbd93c4a548df2990.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/3288eb6f8803450b9931a679ae43dcd6.png
[40b0112acba74a49b6d703d2580a9a00.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/6c37a50a927c4ae29a8b4376bcd748e3.png
[CodeForces - 1846A. Rudolph and Cut the Rope]: https://codeforces.com/problemset/problem/1846/A
[5520342c6a82413c84200049ee7699ef.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/7bd3e6f876694edcb0f81041a573a47a.png
[f0ab58db1c1542b196d58fea1aaf11ff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/67b40b64d44d4078a07dcac624727bde.png
[P1449]: https://www.luogu.com.cn/problem/P1449
[fdad3772f1744dfcb8b2e689022987ee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/b9448d25a6a64a16bcfa6af1a9dce34c.png
[6a05f5e0844141d6bfb0569488b7d370.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/3b15c0875d874c5e954e0fa28b679a9b.png
[CodeForces - 459B. Pashmak and Flowers]: https://codeforces.com/problemset/problem/459/B
[c66bbe7835164b228211e46b264b0444.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/5dfd1bede1504581a8eb164ad551775e.png
[b6166eaaa84a41cab8d3e6bc1cb20e91.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/b91201e1221745e89dac14d98db4aea4.png
[d3a27e64a43441ce9ef796e34bc4a692.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/718c5c698bc5473497c459a331b45e6c.png