第14届蓝桥杯省赛-C++-卷2

姓名：

1.结构化程序所要求的基本结构不包括（） 。

2.若定义 int a=2， b=2， 下列表达式中值不为 4 的是（）

3. 在下列选项中， 不能输出 100 个整数的是（） 。

4.下列叙述中正确的是（） 。

5. 小蓝打羽毛球实行积分赛制， 获胜积 5 分， 打平积 2 分， 失败扣 1 分。 已知小蓝在 20 场积分赛后积 61 分且有 3 场比赛打平， 那么小蓝的胜率为： ( )

属相
我们中国人对老鼠的感情可不一般， 鼠是中国传统十二生肖之首。 那么 2020 年
出生的“20 后”是否都是“鼠宝宝”呢？ 其实不是， 2020 年 1 月 1 日～1 月 24 日出
生的“20 后”， 仍然是“猪宝宝”， 因为他们出生在农历己亥猪年； 大年初一（1 月 25
日） 及之后出生的“20 后”才是“鼠宝宝”。 那么接下来请你判断一下， 以下生日的宝
宝是“猪宝宝” 还是“鼠宝宝”？
输入： 符合常识的两个空格分隔的整数 month,day， 分别代表宝宝出生的月份及
日子， （1<=month<=12, 1<=day<=31） 。
输出： 若是“猪宝宝”请输出"Pig"； 若是“鼠宝宝”请输出"Mouse"。 样例输入：
1 1
样例输出： Pig

写个“Z”
题目描述:2020 年 2 月， 小蓝参加“蓝桥杯大赛青少年创意编程 C++组”选拔赛。 在
一个这么“2”的时间里参赛， 小蓝一时高兴， 忍不住在键盘上敲出了一个会写“2”的程
序。
输入： 一个整数 n(3<=n<=100)
输出： 一个由“*”组成的长、 宽都是 n 的“2”字图形,具体请参见样例。
样例输入 1： 5
样例输出 1：

样例输入 2： 8
样例输出 2：

石头剪刀布
放假期间， 小蓝与电脑对垒， 玩起了一款经典的游戏： “石头剪刀布”。 游戏规则
想必大家已经非常熟悉了： 两边一样则为平局， 否则石头胜于剪刀； 剪刀胜于布； 布
胜于石头。 小蓝与电脑的对垒一共有 n 个回合， 平局或败局得分为 0； 胜局得分取
决于小蓝出手的阵容， 剪刀、 石头、 布各有不同的分值：
出手“石头”赢的话得 r 点分值； 出手“剪刀”赢的话得 s 点分值； 出手“布”赢的
话得 c 点分值；
但是， 在第 i 回合中， 小蓝不能使用在第（i-k） 个回合中使用的阵容。 （在前 k
个回合中， 小蓝可以使用任何阵容。 ）
在游戏开始之前， 电脑已经事先安排好了每回合比赛的阵容， 而小蓝居然未卜先
知了电脑的阵容！ 电脑的出手阵容用字符串 t 给出， 如果 t 的第 i 个字符（1≤i≤n）
为 r， 则代表电脑将在第 i 个回合中出手“石头”。 同样， c 和 s 分别代表“布”和“剪刀”。
那么请你计算一下， 小蓝在游戏中可以获得的最大分值是多少？ 输入:
n k
r s c t
其中： n,k,r,s,c 都是整数， t 是字符串。 2≤n≤20
1≤k≤n−1
1≤r,s,c≤1000
字符串 t 的长度是 n 输出:
小蓝在游戏中可以获得的最大分值。
6 样
例输入:
5 2
8 7 6
rsrcr
样例输出:
27
样例说明：
机器出手的阵容是： 石头、 剪刀、 石头、 布、 石头
则小蓝出手： 布、 石头、 石头、 剪刀、 布， 分值为 6+8+0+7+6=27 分
第 3 回合里， 小蓝不能再出第（3-2=1） 回合里出过的“布”了， 所以选择了平局，
出手“石头”， 得 0 分。

部分排序
一个数列 P 中有 n 个数。 小蓝从中选择位置连续的 k 个数， 并对这 k 个数进行升序排列。 求排序后的数列有多少种?
输入:
n k
P0 P1 ⋯ Pn−1
其中： 所有的输入都是整数， 2≤n≤100， 2≤k≤n， 0≤Pi≤n−1， P0,P1,⋯,Pn−1 数值都不
相同。
输出:部分排序后数列的排列数。

样例输入:
5 3
0 2 1 4 3
样例输出:
2
样例说明： 从原数列抽取连续 3 个数排序后有 2 种可能性: (0,1,2,4,3) 和
(0,2,1,3,4)。

题目的分数值
蓝桥杯 C++青少组的比赛有 n 个问题， 现在请你给这 n 个问题分配分值。
n 个问题已经按从简单到困难排好序， 第 i 个问题的分值是 Ai。 n 个问题的分值
满足如下关系：
1≤A1≤A2≤…≤An≤n。 不同的问题可以具有相同的分值。
主办方希望： 解决更多问题的参赛者的排名更高。 因此， 对于任何解决了 k
（1≤k≤n-1） 个问题的参赛者， 其分数总和一定要小于解决了任何 k + 1 个问题的参
赛者的分数总和。
你有几种分配分值的方法？ 将答案对素数 m 取余后输出。 输入：
整数 n 和 m
其中 2≤n≤5000,9×108<m<109 ， m 为素数。 输出：
分值分配的方案数对 m 取余后的数字样例输入 1：
2 998244353
样例输出 1： 3
样例 1 说明：
2 个题的分值分配有 3 种方案： (1,1), (1,2), (2,2)。
样例输入 2： 3 998244353
样例输出 2： 7
样例 2 说明：
3 个题的分值分配有 7 种方案： (1,1,1), (1,2,2), (1,3,3), (2,2,2), (2,2,3), (2,3,3),
(3,3,3)

凑算式

快速排序
排序在各种场合经常被用到。 快速排序是十分常用的高效率的算法。
其思想是： 先选一个“标尺”， 用它把整个队列过一遍筛子， 以保证： 其左边的元
素都不大于它， 其右边的元素都不小于它。 这样， 排序问题就被分割为两个子区间。
再分别对子区间排序就可以了。
下面的代码是一种实现， 请分析并填写划线部分缺少的代码。

抽签
X 星球要派出一个 5 人组成的观察团前往 W 星。
其中：
A 国最多可以派出 4 人。
B 国最多可以派出 2 人。
C 国最多可以派出 2 人。
....
那么最终派往 W 星的观察团会有多少种国别的不同组合呢？
下面的程序解决了这个问题。
数组 a[] 中既是每个国家可以派出的最多的名额。
程序执行结果为：
DEFFF
CEFFF
CDFFF
CDEFF
CCFFF
CCEFF
CCDFF
CCDEF
BEFFF
BDFFF
BDEFF
BCFFF
BCEFF
BCDFF
BCDEF
....
(以下省略， 总共 101 行)

方格填数（DP）
如下的 10 个格子
     +--+--+--+
             | | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | |
+--+--+--+
填入 0~9 的数字。 要求： 连续的两个数字不能相邻。 （左右、 上下、 对角都算相
邻）
一共有多少种可能的填数方案？ 请填写表示方案数目的整数。

四平方和
四平方和定理， 又称为拉格朗日定理：
每个正整数都可以表示为至多 4 个正整数的平方和。
如果把 0 包括进去， 就正好可以表示为 4 个数的平方和。
比如：
5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2
（^符号表示乘方的意思）
对于一个给定的正整数， 可能存在多种平方和的表示法。
要求你对 4 个数排序：
0 <= a <= b <= c <= d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列， 最后输出第一个表示法
程序输入为一个正整数 N (N<5000000)
要求输出 4 个非负整数， 按从小到大排序， 中间用空格分开
例如， 输入：
5 则
程序应该输出：
0 0 1 2
再例如， 输入：
12
则程序应该输出：
0 2 2 2
再例如， 输入：
773535
则程序应该输出：
1 1 267 838
请严格按要求输出， 不要画蛇添足地打印类似： “请您输入...” 的多余内容。
所有代码放在同一个源文件中， 调试通过后， 拷贝提交该源码。
注意: main 函数需要返回 0
注意: 只使用 ANSI C/ANSI C++ 标准， 不要调用依赖于编译环境或操作系统的特
殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设
置而省略常用头文件