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

这篇具有很好参考价值的文章主要介绍了【ACM】—蓝桥杯大一暑期集训Day2。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🚀欢迎来到本文🚀
🍉个人简介:陈童学哦,目前学习C/C++、算法、Python、Java等方向,一个正在慢慢前行的普通人。
🏀系列专栏:陈童学的日记
💡其他专栏:C++STL,感兴趣的小伙伴可以看看。
🎁希望各位→点赞👍 + 收藏⭐️ + 留言📝 ​
⛱️学习应使你快乐!望与诸君共勉!🏄‍♂️

【ACM】—蓝桥杯大一暑期集训Day2,ACM,ACM,蓝桥杯,算法,c++,单调栈

前言

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

A - 表达式的转换

来源:洛谷P1175 表达式的转换
【ACM】—蓝桥杯大一暑期集训Day2,ACM,ACM,蓝桥杯,算法,c++,单调栈
【ACM】—蓝桥杯大一暑期集训Day2,ACM,ACM,蓝桥杯,算法,c++,单调栈

解题思路

本题是道用栈实现后缀表达式模拟题,但是实现过程还是有点复杂的,好家伙第一题就给我上难度是吧。
主要的就是注意下()以及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
【ACM】—蓝桥杯大一暑期集训Day2,ACM,ACM,蓝桥杯,算法,c++,单调栈
【ACM】—蓝桥杯大一暑期集训Day2,ACM,ACM,蓝桥杯,算法,c++,单调栈

解题思路

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

示例代码

#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
【ACM】—蓝桥杯大一暑期集训Day2,ACM,ACM,蓝桥杯,算法,c++,单调栈
【ACM】—蓝桥杯大一暑期集训Day2,ACM,ACM,蓝桥杯,算法,c++,单调栈
【ACM】—蓝桥杯大一暑期集训Day2,ACM,ACM,蓝桥杯,算法,c++,单调栈

解题思路

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

【ACM】—蓝桥杯大一暑期集训Day2,ACM,ACM,蓝桥杯,算法,c++,单调栈
【ACM】—蓝桥杯大一暑期集训Day2,ACM,ACM,蓝桥杯,算法,c++,单调栈

解题思路

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

示例代码

#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 后缀表达式
【ACM】—蓝桥杯大一暑期集训Day2,ACM,ACM,蓝桥杯,算法,c++,单调栈
【ACM】—蓝桥杯大一暑期集训Day2,ACM,ACM,蓝桥杯,算法,c++,单调栈

解题思路

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

示例代码

#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
【ACM】—蓝桥杯大一暑期集训Day2,ACM,ACM,蓝桥杯,算法,c++,单调栈

【ACM】—蓝桥杯大一暑期集训Day2,ACM,ACM,蓝桥杯,算法,c++,单调栈

【ACM】—蓝桥杯大一暑期集训Day2,ACM,ACM,蓝桥杯,算法,c++,单调栈

解题思路

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

示例代码

#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的题主要考察的也是一些基础的算法,有些稍复杂。
算法:单调栈、线性结构、模拟、暴力
感悟:这些算法算也是较基础的,但还需多加练习达到更快解题
总结:每个算法都有其巧妙处,一些模拟题也是较为繁琐很是考察逻辑思维的文章来源地址https://www.toymoban.com/news/detail-566431.html

到了这里,关于【ACM】—蓝桥杯大一暑期集训Day2的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法竞赛备赛之经典数据结构训练提升,暑期集训营培训

    我们将结构体和指针结合来实现链表 我们算法主要是用数组来模拟链表,这样效率会高一些。 数组模拟单链表 邻接表:存储图和树 实现一个单链表,链表初始为空,支持三种操作: 向链表头插入一个数 删除第k个插入的数后面的数 在第k个前面插入一个数 数组模拟双链表的

    2024年02月16日
    浏览(52)
  • 算法竞赛备赛之搜索与图论训练提升,暑期集训营培训

    目录 1.DFS和BFS 1.1.DFS深度优先搜索 1.2.BFS广度优先搜索 2.树与图的遍历:拓扑排序 3.最短路  3.1.迪杰斯特拉算法 3.2.贝尔曼算法 3.3.SPFA算法 3.4.多源汇最短路Floy算法 4.最小生成树 4.1.普利姆算法 4.2.克鲁斯卡尔算法 5.二分图:染色法,匈牙利算法 5.1.染色法 5.2.匈牙利算法 深度优

    2024年02月13日
    浏览(34)
  • 蓝桥杯·3月份刷题集训Day03

    本篇博客旨在记录自已打卡蓝桥杯3月份刷题集训,同时会有自己的思路及代码解答希望可以给小伙伴一些帮助。本人也是算法小白,水平有限,如果文章中有什么错误之处,希望小伙伴们可以在评论区指出来,共勉💪。 A1、扫雷 题目 :在一个 n 行 m 列的方格图上有一些位置

    2023年04月09日
    浏览(34)
  • 蓝桥杯·3月份刷题集训Day07

    本篇博客旨在记录自已打卡蓝桥杯3月份刷题集训,同时会有自己的思路及代码解答希望可以给小伙伴一些帮助。本人也是算法小白,水平有限,如果文章中有什么错误之处,希望小伙伴们可以在评论区指出来,共勉💪。 A1、约数个数 题目 : 本题为填空题,只需要算出结果

    2023年04月09日
    浏览(39)
  • 蓝桥杯打卡Day2

    文章目录 糖果分享游戏 玛雅人的密码 本题思路: 本题是一道模拟题,最终需要每个人得到相同的糖果,那么此时我们开辟一个数组用来保存每个人分一半的结果,然后每个人都需要从左边拿到对方糖果,那么左边就是可以计算为(n+i-1)%n。然后对于糖果为奇数的人进行++操作。

    2024年02月09日
    浏览(39)
  • 蓝桥杯省赛7日集训-简单数论 Day1-Day2

    这是一个比较简单的质因数分解问题,可以使用试除法求解。具体实现过程如下: 从标准输入中读取正整数 n。 从 2 开始依次尝试将 n 进行除法运算,如果 n 能够被当前的数整除,则说明当前数是 n 的一个质因数,将 n 除以当前数,然后继续尝试除以当前数,直到 n 不能被当

    2023年04月08日
    浏览(31)
  • 蓝桥杯真题(Python)每日练Day2

    对于本题首先确定其数据结构为优先队列,即邮费最小的衣服优先寄,算法符合贪心算法。 可以直接使用queue库的PriorityQueue方法实现优先队列。 关于PriorityQueue的使用方法主要有: 尤其注意使用put()函数时,第一个参数priority值越小优先级越高,也就是对首总是最小值。 其实

    2024年01月21日
    浏览(42)
  • 蓝桥杯 题库 简单 每日十题 day2

    题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 小蓝有很多数字卡片,每张卡片上都是数字 0 到 9。 小蓝准备用这些卡片来拼一些数,他想从 1 开始拼出正整数,每拼一个,就保存起来,卡片就不能用来拼其它数了。 小蓝想知道自

    2024年02月07日
    浏览(41)
  • 蓝桥杯备赛 | 洛谷做题打卡day2

    ​ 题目来源:洛谷P2670 [NOIP2015 普及组] 扫雷游戏 NOIP2015 普及组 T2 扫雷游戏是一款十分经典的单机小游戏。在 n n n 行 m m m 列的雷区中有一些格子含有地雷(称之为地雷格),其他格子不含地雷(称之为非地雷格)。玩家翻开一个非地雷格时,该格将会出现一个数字——提示

    2024年01月16日
    浏览(58)
  • 贪心算法练习day2

    1)初始化最小字母为‘Z’,确保任何字母都能与之比较 2)遍历单词,找到当前未删除字母中的最小字母 3)获取当前位置的字母  current = word.charAt(i); 4)删除最小字母之前的所有字母  word=word.substring(index+1); 5)  将最小字母添加到结果字符,更新剩余可删除字母数量 t -=

    2024年02月20日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包