第十届蓝桥杯大赛青少年省赛C++组试题真题（2019年）

编程题

第 1 题 问答题

水下探测器

水下探测器可以潜入湖中在任意水深进行科学探索。湖水的最大深度为h米即它在湖底时到水面的距离，0<=h<=100;探测器最初的水下深度 s米，0<=s<=100;

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

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

在执行到无效指令时，探测器不做任何操作而继续执行下一指令。编程实现:

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

输入:

第一行:h和s，以空格分开。0<=s<=h<=100第二行:长度不超过 100的指令字符串，串中仅包含字母u或 d输出:

代表探测器在执行指令后的水下深度的数字样例输入:

9 1
uduudd

样例输出:

2

样例数据分析:水深9米,探测器在水下1米处

字符u代表向上1米,探测器上浮到0米处

字符d代表向下1米,探测器下沉到1米处

字符u代表向上1米,探测器上浮到0米处字符u代表向上1米探测器已经在水面,不能上浮,依然在0米处字符d代表向下1米,探测器下沉到1米处字符d代表向下1米,探测器下沉到2米处

最终结果为2

第 2 题 问答题

猫吃鱼

明明家从1号站点出发，开车去旅游，一共要经过n个站点，依次为 2、3......n。由于明明带上了心爱的小猫，在每个站点都要为小猫提供一条鱼用做美餐(包括1号站点)。除了1号站点只能吃1号站点买的鱼，其他站点既可以吃当地买的鱼，也可吃之前经过的站点买了存入车载冰箱中的鱼。

但车载冰箱消耗的电能来自汽油，所以每条鱼用冰箱保存到下一站的费用与各个站点的汽油价格有关为使问题简化，我们约定:

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

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

即:每条鱼的费用既包括购买时的费用，也包括用冰箱保存鱼的费用。编程实现:

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

入:

第一行: 站点数n，1 < n < 100

接下来的n行:每行两个以空格分隔的正整数，表示:这一站买一条鱼的费用，以及从这一站把每条鱼保存到下一站的费用，两个费用均为小于 10000 的正整数输出:

最小总费用，是一个正整数

样例输入:

5
63
71
32
83
95

样例输出

29

样例数据分析:

第一行数据5代表一共5站

第二行数据63代表本站购买鱼6元,运费3元,第一站必须一定先购买一条 总花费6元

第三行数据71代表本站购买鱼7元,运费1元,从上一站最小花费+运费9元大于本站购买的费用7,所以选择从本站购买鱼总花费 6+7=13元

第四行数据32代表本站购买鱼3元,运费2元,从上一站最小花费+运费8元大于本站购买的费用3,所以选择从本站购买鱼,总花费 6+7+3=16元

第五行数据83代表本站购买鱼8元,运费3元从上一站最小花费+运费5元,小于本站购买的费用8,所以选择从上站花费加上本站运费总花费6+7+3+5=21元

第六行数据95代表本站购买鱼9元 运费5元,从上一站最小花费+运费8元,小于本站购买的费用9,所以选择从上一站花费加上本站运费总花费6+7+3+5+8=29元

最终总花费为29元

第 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
1 0

样例1输出:

1

样例2输入:

3 4
321
213
231
312

样例2输出:

-2

样例数据分析

样例1:

第一行3 4代表3个品牌,4个评委

第一轮投票,3个评委优先选择1号品牌,1个评委选择2号品牌,品牌3得票最少,淘汰掉

第二轮投票3个评委优先选择1号品牌,1个评委选择2号品牌,品牌2得票最少,淘汰掉,淘汰2号品牌后,只剩一个1号品牌,1号品牌胜出

最终结果1

样例2:

第一行34代表3个品牌4个评委

第一轮投票,2个评委选择2号品牌,两个评委选择3号品牌,1号得票最少,淘汰掉

第二轮投票,2个评委选择2号品牌,两个评委选择3号品牌,由于只剩下两个品牌,且并列最少,都是2票代表评选失败需要输出最后一轮票数2的相反数-2

最终结果-2

第 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 

样例数据分析:

第一行数据1094代表最多能提起重量10购物袋体积9,4种商品

第二行数据代表第1件商品重量8体积3,让利金额4

第三行数据代表第2件商品重量5,体积4,让利金额5

第四行数据代表第3件商品重量3,体积7,让利金额7

第五行数据代表第4件商品重量4体积5让利金额4

创建一个三维数组 yh[n+1][w+1][v+1] 记录在第n个物品,w重量,v体积时 最优策略2

只考虑一个物品的时候(纵向代表重量,横向代表体积,数据代表最大优惠)

考虑前两个物品的时候

考虑前三个物品的时候

考虑前四个物品的时候

最终结果,最大优惠为9.同时需要额外记录在在不同商品数量,不同重量和体积的情况下,如何购买商品

第 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
L Q

样例1输出:

0

样例2输入:

3 3
LSB
QBQ
BSL

样例2输出:

-1

样例3输入:

4 4
BLQB
BBQS
SBQL
QQQQ

样例3输出:

2

样例数据分析:

样例1:

第一行数据33代表是3行3列的迷宫

第1步,寻找L

LSB
QBQ
BSL

第2步在L的上下左右寻找Q

LSB
QBQ
BSL

第3步在Q的上下左右寻找B

LsB
QBQ
BSL

第4步在B的上下左右寻找S

LSB
QBQ
BSL

如此当重复到10次的时候,仍可以继续走,代表进入无限循环

因为3行3列最多9个格子,能走10步就代表一定进入无限循环

输出-1

样例2:

第一行数据44代表是4行4列的迷宫

第1步,寻找起点L

BLQB
BBQS
SBQL
QQQQ

第2步在L的上下左右寻找Q

BLQB
BBQS
SBQL
QQQQ

第3步在Q的上下左右寻找B

BLQB
BBQS
SBQL
QQQQ

第4步在B的上下左右寻找S

BLQB
BBQS
SBQL
QQQQ

第5步在S的上下左右寻找L

BLQB
BBQS
SBQL
QQQQ

第6步在L的上下左右寻找Q

BLQB
BBQS
SBQL
QQQQ

第7步在Q的上下左右寻找B

BLQB
BBQS
SBQL
QQQQ

第8步在B的上下左右寻找S

BLQB
BBQS
SBQL
QQQQ

第9步在S的上下左右寻找L

因为找不到L了,则代表迷宫走到尽头,一共走了8步,LQBS一共4个字符,所以走了8/4=2共计2次LQBS,输出2