2019第十届蓝桥杯大赛青少年创意编程省赛C++组试题解析

本文涉及的产品
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
简介: 2019第十届蓝桥杯大赛青少年创意编程省赛C++组试题解析

1、水下探测器

水下探测器可以潜入湖中在任意水深进行科学探索。

湖水的最大深度为 h 米,即它在湖底时到水面的距离,0<=h<=100;

探测器最初的水下深度为 s 米,0<=s<=100;

当探测器不在水面(当前深度大于 0)时,每个 u 指令可使它上浮 1 米,而当探测器在水面时,u 指令是无效的;

当探测器不在湖底(当前深度小于 h)时,每个 d 指令可使它下沉 1 米,而当探测器在湖底时,d 指令是无效的;

在执行到无效指令时,探测器不做任何操作而继续执行下一指令。

编程实现:

根据给定的 h、s 和一个指令序列(由字符 u、d 组成的字符串,长度不超过 100),求出执行完整的指令序列后,探测器的水下深度。

输入:

第一行:h 和 s,以空格分开。0<=s<=h<=100

第二行:长度不超过 100 的指令字符串,串中仅包含字母 u 或 d

输出:

代表探测器在执行指令后的水下深度的数字。

样例输入:

9 1

uduudd

样例输出:

2

样例数据分析:

考察知识:

基础语法,字符串,循环,条件判断

参考代码:

1. #include <stdio.h>
2. #include <iostream>
3. using namespace std;
4. int main(int argc, char *argv[])
5. {
6.  int h,s;
7.  scanf("%d %d",&h,&s);
8.  char n[101];
9.  scanf("%c",n);
10.   int l=strlen(n);
11.   for(int i=0;i<l;i++){
12.     if(n[i]=='u')
13.       if(s>0)s--;
14.     else if(n[i]=='d')
15.       if(s<h)s++; 
16.    }
17.    printf("%d",s);
18.   return 0;
19. }

2、猫吃鱼

明明家从 1 号站点出发,开车去旅游,一共要经过 n 个站点,依次为 2、3……n。

由于明明带上了心爱的小猫,在每个站点都要为小猫提供一条鱼用做美餐(包括 1 号站点)。

除了 1 号站点只能吃 1 号站点买的鱼,其他站点既可以吃当地买的鱼,也可吃之前经过的站点买了存入车载冰箱中的鱼。

但车载冰箱消耗的电能来自汽油,所以每条鱼用冰箱保存到下一站的费用与各个站点的汽油价格有关。

为使问题简化,我们约定:

(1)车从某站开出时油箱中都是此站点刚加的汽油。

(2)车载冰箱能容纳一路上需要的所有鱼。

即:每条鱼的费用既包括购买时的费用,也包括用冰箱保存鱼的费用。

编程实现:

为了降低小猫吃鱼的总代价,明明预先上网查到了这 n 个站点的鱼价和汽油价格。并据此算出每个站点买一条鱼的费用以及从该站点到下一站用冰箱保存一条鱼的费用。你能帮明明算出这一路上小猫吃鱼的最小总费用吗?

输入:

第一行:站点数 n,1<n<100。

接下来的 n 行:每行两个以空格分隔的正整数,表示:这一站买一条鱼的费用,以及从这一站把每条

鱼保存到下一站的费用,两个费用均为小于 10000 的正整数。

输出:

最小总费用,是一个正整数。

样例输入:

5

6 3

7 1

3 2

8 3

9 5

样例输出:

29

参考代码:

1. #include <iostream>
2. #include <stdio.h>
3. using namespace std;
4. int m[100][3];
5. int main(int argc, char *argv[])
6. {
7.  int n;
8.  scanf("%d",&n);
9.  for(int i=1;i<=n;i++)
10.     scanf("%d %d",&m[i][1],&m[i][2]);
11.   int sum=0,min=99999;
12.   for(int i=1;i<=n;i++){
13.     if(min>m[i][1]) min=m[i][1];
14.     sum+=min;
15.     min+=m[i][2];
16.   }
17.   printf("%d\n",sum);
18.   return 0;
19. }

3、评选最佳品牌

n 个评委投票,在 m 个商品中评选一个最佳品牌。

评选采用多轮淘汰制,即:每轮投票,淘汰掉得票最少的候选品牌(得票并列最少的品牌一起淘汰)。

如此一轮轮淘汰下去,如果最后只剩下一个品牌当选,即告评选成功。

但如果在某轮投票中,当时未被淘汰的所有候选品牌(大于等于两个品牌)都并列得票最少,即告评选失败。

如果评选成功就输出当选品牌号。否则输出最后一轮评选时唯一选票数的相反数。

在评选流程中,每个评委的态度都可用一个序列来表示;例如当 m=5 时,某评委的评选态度序列为:3、

5、1、2、4,则表示该评委:优先投 3 号,当 3 号被淘汰时投 5 号,当 3 和 5 都被淘汰时投 1,当 3、5、1 都被淘汰时投 2,仅剩 4 号时才投 4 号品牌的票。

选票的序列中可以表示弃权,用 0 来表示,例如当 m=5 时,某评委的评选态度序列为:3、5、0,则表示该评委:优先投 3 号,当 3 号被淘汰时投 5 号,其它情况下不投任何品牌的票。

编程实现:

请你编一个程序,模拟各轮投票的过程,得到评选结果。

输入:

第一行:m(0<m<10,表示参加评选的品牌数)和 N(1<n<1000,表示参加投票的评委数),之间以空格分隔接下来的 n 行:每行都是长度不超 m 的数字字符串,每个字符串表示一个评委的评选态度。

输出:

评选结果。

样例 1 输入:

3 4

123

213

132

10

样例 1 输出:

1

样例 2 输入:

3 4

321

213

231

312

样例 2 输出:

-2

样例数据分析:

考察知识:

字符串,桶排序,模拟算法

参考代码:

1. #include<iostream>
2. #include<algorithm>
3. #include<cstring>
4. #include<fstream>
5. using namespace std;
6. const int M=15,N=1010;
7. int g[N][M];//存储评委投票态度 
8. int piao[M];//得票桶 
9. int st[M];//品牌标识桶 
10. bool success=true;
11. int last_piaoshu;
12. int last_pinpai; 
13. int n,m;//n个评委 m个品牌
14. void pingxuan()
15. {
16.   while(1){
17.     memset(piao,0,sizeof(piao));
18.     for(int i=1;i<=n;i++)
19.       for(int j=1;j<M;j++){
20.         int k=g[i][j];
21.         if(k==0) break;//弃权票
22.         if(st[k])continue;//品牌已淘汰
23.         piao[k]++;//投票入桶
24.         break;//投票完成换下个评委 
25.       }
26.     //寻找最大票数和最小票数
27.     int min=1001,max=-1001;
28.     for(int i=1;i<M;i++){
29.       if(piao[i]<min && !st[i])min=piao[i];
30.       if(piao[i]>max && !st[i])max=piao[i];
31.     }
32.     if(max>min){//淘汰掉最小得票的品牌 
33.       for(int i=1;i<M;i++)
34.         if(piao[i]==min && st[i]==false)st[i]=true;//标志淘汰 
35.       continue;//进入下一轮评选 
36.     }
37.     else{
38.       int sum=0;
39.       for(int i=1;i<M;i++)//搜索有几个最小票数的品牌 
40.         if(piao[i]==min)sum++,last_pinpai=i; 
41.       if(sum==1)return;//只剩一个品牌,结束循环
42.       else{//剩余多个品牌,评选失败 
43.         last_piaoshu=min;//保留最后一轮的得票 
44.         success=false;//标识失败 
45.         return ;//评选结束 退出循环 
46.       } 
47.     } 
48.   }
49. } 
50. int main()
51. {
52.   //freopen("king.in","r",stdin);
53.   cin>>m>>n;
54.   for(int i=1;i<=n;i++){
55.     string str;
56.     cin>>str;
57.     for(int j=0;j<str.size();j++)
58.       g[i][j+1]=str[j]-'0';
59.   }
60.   pingxuan();
61.   if(success) cout<<last_pinpai<<endl;
62.   else cout<<"-"<<last_piaoshu<<endl;
63.   return 0;   
64. }

4、最大购物优惠

小惠听说超市正在打折促销,要制订一个得到最大优惠的购物计划。

小惠的体力可以提起 w 单位重量的东西,还有一个能装 V 个单位体积的购物袋,并详细了解了各打折商品的重量、体积及此商品实际优惠的金额。她想在自己体力的限度和购物袋容积限度内,尽可能多地得到购物优惠。

超市规定这些打折商品每种只能购买一件。

编程实现:

请你编写程序,制定一个购买商品的计划,求出小惠能得到的最大优惠金额和实际应购买的各商品序号。

输入:

第一行:依次为 w、v 和 n(n 为商品种类数),所有数值均为不超过 100 的正整数

接下来的 n 行:每行有三个整数,依次为某种商品的重量、体积和让利金额,数值间以空格分开,所有数值均为不超过 100 的正整数

输出:

第一行:小惠能够得到的最大让利金额

第二行:依次为从小到大排列的商品序号,序号从 1 开始,序号间用空格分开。若第二行输出的序列不唯一,则输出其最小字典序。

样例输入:

10 9 4

8 3 6

5 4 5

3 7 7

4 5 4

样例输出:

9

2 4

样例数据分析:

考察知识:

动态规划,二维费用的背包问题,在01背包问题的基础上增加一个费用维度

状态转移方程:

yh[i][j][k]=max(yh[i-1][j][k],yh[i-1][j-w[i]][k-v[i]]+n[i])

经典01背包问题解(https://blog.csdn.net/qq_38410730/article/details/81667885)

总体思路:

1.先从后往前推,得到最大让利金额,并形成具体方案(仿照最短路问题,从后往前)

2.再从前往后推,得到具体方案的字典序

参考代码:

1. #include<iostream>
2. #include<algorithm>
3. #include<fstream>
4. using namespace std;
5. const int N=110;
6. int w[N],v[N],p[N];
7. int f[N][N][N];
8. int main()
9. {
10.   //freopen("shopping.in","r",stdin);
11.   int W,V,n;
12.   cin>>W>>V>>n;
13.   for(int i=1;i<=n;i++) cin>>w[i]>>v[i]>>p[i];
14.   //求最短路,从后往前推 
15.   for(int i=n;i>=1;i--){
16.     for(int j=0;j<=W;j++)
17.       for(int k=0;k<=V;k++){
18.         f[i][j][k]=f[i+1][j][k];
19.         if(j>=w[i] && k>=v[i])
20.           f[i][j][k]=max(f[i][j][k],f[i+1][j-w[i]][k-v[i]]+p[i]);
21.         }
22.   }
23.   cout<<f[1][W][V]<<endl;
24.   //字典序向后推 
25.   int j=W,k=V;
26.   for(int i=1;i<=n;i++)
27.     if(j>=w[i] && k>=v[i] && f[i][j][k]==f[i+1][j-w[i]][k-v[i]]+p[i]){
28.       cout<<i<<' ';
29.       j-=w[i],k-=v[i];
30.     }
31.   puts("");
32.   return 0;
33. }

5、迷宫

把一个 n 行 m 列的字符阵列看做一个迷宫,迷宫仅包含 L、Q、B、S 中的大写字母(蓝桥杯赛的汉语拼音首字母)。

初始时,你可以从任意一个“L”字母开始,移向相邻的“Q”字母,然后从此“Q”字母出发,移向相邻的“B”字母,然后从此“B”字母出发,移向相邻的“S”字母……。这样,你就算是走过了一个“LQBS”字符序列。

接下来,仍然可以从此“S”字母出发,移向相邻的“L”字母……,重复上述的动作,你就可以不断地走过“LQBS”序列。

请注意,所谓相邻仅包含上、下、左、右 4 个方向,且只能从 L->Q,从 Q->B,从 B->S,从 S->L。

可以想像,由于选择的出发点不同,我们有可能在迷宫中走过无数次的“LQBS”,或者是有限次的“LQBS”,

或者一次也走不了。

编程实现:

请你编写程序,求出在给定的迷宫中,我们最多可以走过多少次“LQBS”?

输入:

第一行:正整数 n,m,表示迷宫的规模为 n 行 m 列,0<m<100,0<n<100

接下来的 n 行:每行 m 个符合题意的字母,字母间无空格。

输出:

一个整数。即:如果在迷宫中可以无限次的走过“LQBS”,输出-1,否则,输出可以走过“LQBS”的最多次数。

样例 1 输入:

1 2

LQ

样例 1 输出:

0

样例 2 输入:

3 3

LSB

QBQ

BSL

样例 2 输出:

-1

样例 3 输入:

4 4

BLQB

BBQS

SBQL

QQQQ

样例 3 输出:

2

样例数据分析:

考察知识:

搜索与回朔

由于笔者的学员暂时未学到搜索与回朔算法,所以采用循环遍历类似穷举算法进行题解

参考代码:

1. #include<iostream>
2. #include<algorithm>
3. #include<fstream>
4. using namespace std;
5. const int N=110;
6. char g[N][N];
7. int f[N][N];
8. int n,m;
9. bool wuxian;
10. int mstep,step=1;
11. int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0}; 
12. void dfs(int x,int y){
13.   for(int i=0;i<4;i++){
14.     int xx=x+dx[i],yy=y+dy[i];
15.     if(xx<0||xx>n-1||yy<0||yy>m-1)continue;//越界跳过
16.     if((g[x][y]=='L' && g[xx][yy]=='Q')||(g[x][y]=='Q' && g[xx][yy]=='B')||
17.     (g[x][y]=='B' && g[xx][yy]=='S')||(g[x][y]=='S' && g[xx][yy]=='L')){
18.       if(f[xx][yy]){
19.         wuxian=true;
20.         return ;
21.       }
22.       f[xx][yy]=1;
23.       step++;
24.       mstep=max(mstep,step);
25.       dfs(xx,yy);
26.       f[xx][yy]=0;
27.       step--;
28.     }   
29.   }
30.   return ;
31. } 
32. int main()
33. {
34.   //freopen("LQBS3.in","r",stdin);
35.   cin>>n>>m;
36.   for(int i=0;i<n;i++) cin>>g[i];
37.   for(int i=0;i<n;i++){
38.     for(int j=0;j<m;j++){
39.       if(g[i][j]=='L'){
40.         memset(f,0,sizeof(f));
41.         dfs(i,j);
42.       }
43.       if(wuxian){
44.         cout<<-1<<endl;
45.         return 0;
46.       }
47.     }
48.   }
49.   cout<<mstep/4<<endl;
50. 
51.   return 0;
52. }

 

相关文章
|
1天前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
1天前
|
安全 编译器 C语言
【C++篇】深度解析类与对象(中)
在上一篇博客中,我们学习了C++类与对象的基础内容。这一次,我们将深入探讨C++类的关键特性,包括构造函数、析构函数、拷贝构造函数、赋值运算符重载、以及取地址运算符的重载。这些内容是理解面向对象编程的关键,也帮助我们更好地掌握C++内存管理的细节和编码的高级技巧。
|
1天前
|
存储 程序员 C语言
【C++篇】深度解析类与对象(上)
在C++中,类和对象是面向对象编程的基础组成部分。通过类,程序员可以对现实世界的实体进行模拟和抽象。类的基本概念包括成员变量、成员函数、访问控制等。本篇博客将介绍C++类与对象的基础知识,为后续学习打下良好的基础。
|
2月前
|
存储 算法 安全
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
|
2月前
|
存储 缓存 Java
Java 并发编程——volatile 关键字解析
本文介绍了Java线程中的`volatile`关键字及其与`synchronized`锁的区别。`volatile`保证了变量的可见性和一定的有序性,但不能保证原子性。它通过内存屏障实现,避免指令重排序,确保线程间数据一致。相比`synchronized`,`volatile`性能更优,适用于简单状态标记和某些特定场景,如单例模式中的双重检查锁定。文中还解释了Java内存模型的基本概念,包括主内存、工作内存及并发编程中的原子性、可见性和有序性。
Java 并发编程——volatile 关键字解析
|
2月前
|
安全 编译器 C++
C++ `noexcept` 关键字的深入解析
`noexcept` 关键字在 C++ 中用于指示函数不会抛出异常,有助于编译器优化和提高程序的可靠性。它可以减少代码大小、提高执行效率,并增强程序的稳定性和可预测性。`noexcept` 还可以影响函数重载和模板特化的决策。使用时需谨慎,确保函数确实不会抛出异常,否则可能导致程序崩溃。通过合理使用 `noexcept`,开发者可以编写出更高效、更可靠的 C++ 代码。
63 1
|
4天前
|
编译器 C语言 C++
类和对象的简述(c++篇)
类和对象的简述(c++篇)
|
1月前
|
C++ 芯片
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
70 19
|
1月前
|
存储 编译器 数据安全/隐私保护
【C++面向对象——类与对象】CPU类(头歌实践教学平台习题)【合集】
声明一个CPU类,包含等级(rank)、频率(frequency)、电压(voltage)等属性,以及两个公有成员函数run、stop。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。​ 相关知识 类的声明和使用。 类的声明和对象的声明。 构造函数和析构函数的执行。 一、类的声明和使用 1.类的声明基础 在C++中,类是创建对象的蓝图。类的声明定义了类的成员,包括数据成员(变量)和成员函数(方法)。一个简单的类声明示例如下: classMyClass{ public: int
52 13
|
1月前
|
编译器 数据安全/隐私保护 C++
【C++面向对象——继承与派生】派生类的应用(头歌实践教学平台习题)【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括: 1. **类的继承关系基础概念**:介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**:详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**:解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类,添加特定属性并测试这些类的功能。最终通过创建教师和助教实例,验证代码
54 5

推荐镜像

更多