py|第十三届蓝桥杯大赛软件赛省赛 Python 大学 B 组

【py|第十三届蓝桥杯大赛软件赛省赛 Python 大学 B 组】第十三届蓝桥杯大赛软件赛省赛 Python 大学 B 组
第十三届蓝桥杯大赛软件赛省赛
Python 大学 B 组
【考生须知】
考试开始后,选手首先下载题目,并使用考场现场公布的解压密码解压试
题。
考试时间为 4 小时。考试期间选手可浏览自己已经提交的答案,被浏览的
答案允许拷贝。时间截止后,将无法继续提交或浏览答案。
对同一题目,选手可多次提交答案,以最后一次提交的答案为准。
选手必须通过浏览器方式提交自己的答案。选手在其它位置的作答或其它
方式提交的答案无效。
试题包含“结果填空”和“程序设计”两种题型。
结果填空题:要求选手根据题目描述直接填写结果。求解方式不限。不要
求源代码。把结果填空的答案直接通过网页提交即可,不要书写多余的内容。
程序设计题:要求选手设计的程序对于给定的输入能给出正确的输出结果。
考生的程序只有能运行出正确结果才有机会得分。
注意:在评卷时使用的输入数据与试卷中给出的示例数据可能是不同的。
选手的程序必须是通用的,不能只对试卷中给定的数据有效。
所有源码必须在同一文件中。调试通过后,拷贝提交。
对于编程题目,不能使用诸如绘图、硬件操作或与操作系统相关的 API。
注意: 所有依赖的模块(如 math)必须明确地在源文件中 import。只能
使用 python 自带的模块,使用 pip 等安装的扩展模块无法使用。
所有源码必须在同一文件中。调试通过后,拷贝提交。
第十三届蓝桥杯大赛软件赛省赛 1
第十三届蓝桥杯大赛软件赛省赛 Python 大学 B 组
试题 A: 排列字母
本题总分:5 分
【问题描述】
小蓝要把一个字符串中的字母按其在字母表中的顺序排列。
例如,LANQIAO 排列后为 AAILNOQ。
又如,GOODGOODSTUDYDAYDAYUP 排列后为 AADDDDDGGOOOOPSTUUYYY

请问对于以下字符串,排列之后字符串是什么?
WHERETHEREISAWILLTHEREISAWAY
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一
个由大写字母组成的字符串,在提交答案时只填写这个字符串,填写多余的内
容将无法得分。
试题 A: 排列字母 2
第十三届蓝桥杯大赛软件赛省赛 Python 大学 B 组
试题 B: 寻找整数
本题总分:5 分
【问题描述】
有一个不超过 1017 的正整数 n,知道这个数除以 2 至 49 后的余数如下表
所示,求这个正整数最小是多少。
a n mod a a n mod a a n mod a a n mod a
2 1 14 11 26 23 38 37
3 2 15 14 27 20 39 23
4 1 16 9 28 25 40 9
5 4 17 0 29 16 41 1
6 5 18 11 30 29 42 11
7 4 19 18 31 27 43 11
8 1 20 9 32 25 44 33
9 2 21 11 33 11 45 29
10 9 22 11 34 17 46 15
11 0 23 15 35 4 47 5
12 5 24 17 36 29 48 41
13 10 25 9 37 22 49 46
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一
个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
试题 B: 寻找整数 3
第十三届蓝桥杯大赛软件赛省赛 Python 大学 B 组
试题 C: 纸张尺寸
时间限制: 1.0s 内存限制: 512.0MB 本题总分:10 分
【问题描述】
在 ISO 国际标准中定义了 A0 纸张的大小为 1189mm × 841mm,将 A0 纸
沿长边对折后为 A1 纸,大小为 841mm × 594mm,在对折的过程中长度直接取
下整(实际裁剪时可能有损耗)。将 A1 纸沿长边对折后为 A2 纸,依此类推。
输入纸张的名称,请输出纸张的大小。
【输入格式】
输入一行包含一个字符串表示纸张的名称,该名称一定是 A0、A1、A2、
A3、A4、A5、A6、A7、A8、A9 之一。
【输出格式】
输出两行,每行包含一个整数,依次表示长边和短边的长度。
【样例输入 1】
A0
【样例输出 1】
1189
841
【样例输入 2】
A1
【样例输出 2】
841
594
试题 C: 纸张尺寸 4
第十三届蓝桥杯大赛软件赛省赛 Python 大学 B 组
试题 D: 数位排序
时间限制: 1.0s 内存限制: 512.0MB 本题总分:10 分
【问题描述】
小蓝对一个数的数位之和很感兴趣,今天他要按照数位之和给数排序。当
两个数各个数位之和不同时,将数位和较小的排在前面,当数位之和相等时,
将数值小的排在前面。
例如,2022 排在 409 前面,因为 2022 的数位之和是 6,小于 409 的数位
之和 13。
又如,6 排在 2022 前面,因为它们的数位之和相同,而 6 小于 2022。
给定正整数 n,m,请问对 1 到 n 采用这种方法排序时,排在第 m 个的元
素是多少?
【输入格式】
输入第一行包含一个正整数 n。
第二行包含一个正整数 m。
【输出格式】
输出一行包含一个整数,表示答案。
【样例输入】
13
5
【样例输出】
3
试题 D: 数位排序 5
第十三届蓝桥杯大赛软件赛省赛 Python 大学 B 组
【样例说明】
1 到 13 的排序为:1, 10, 2, 11, 3, 12, 4, 13, 5, 6, 7, 8, 9。第 5 个数为 3。
【评测用例规模与约定】
对于 30% 的评测用例,1 ≤ m ≤ n ≤ 300。
对于 50% 的评测用例,1 ≤ m ≤ n ≤ 1000。
对于所有评测用例,1 ≤ m ≤ n ≤ 106。
试题 D: 数位排序 6
第十三届蓝桥杯大赛软件赛省赛Python大学B组
试题 E: 蜂巢
时间限制: 1.0s 内存限制: 512.0MB 本题总分:15 分
【问题描述】
蜂巢由大量的六边形拼接而成,定义蜂巢中的方向为:0 表示正西方向,1
表示西偏北 60?,2 表示东偏北 60?,3 表示正东,4 表示东偏南 60?,5 表示西
偏南 60?。
对于给定的一点 O,我们以 O 为原点定义坐标系,如果一个点 A 由 O 点
先向 d 方向走 p 步再向 (d + 2) mod 6 方向(d 的顺时针 120? 方向)走 q 步到
达,则这个点的坐标定义为 (d, p, q)。在蜂窝中,一个点的坐标可能有多种。
下图给出了点 B(0, 5, 3) 和点 C(2, 3, 2) 的示意。
给定点 (d1, p1, q1) 和点 (d2, p2, q2),请问他们之间最少走多少步可以到达?
【输入格式】
输入一行包含 6 个整数 d1, p1, q1, d2, p2, q2 表示两个点的坐标,相邻两个整
数之间使用一个空格分隔。
【输出格式】
输出一行包含一个整数表示两点之间最少走多少步可以到达。
【样例输入】
0 5 3 2 3 2
试题E: 蜂巢 7
第十三届蓝桥杯大赛软件赛省赛 Python 大学 B 组
【样例输出】
7
【评测用例规模与约定】
对于 25% 的评测用例,p1, p2 ≤ 103 ;
对于 50% 的评测用例,p1, p2 ≤ 105 ;
对于 75% 的评测用例,p1, p2 ≤ 107 ;
对于所有评测用例,0 ≤ d1, d2 ≤ 5,0 ≤ q1 < p1 ≤ 109,0 ≤ q2 < p2 ≤ 109 。
试题 E: 蜂巢 8
第十三届蓝桥杯大赛软件赛省赛 Python 大学 B 组
试题 F: 消除游戏
时间限制: 3.0s 内存限制: 512.0MB 本题总分:15 分
【问题描述】
在一个字符串 S 中,如果 S i = S i?1 且 S i , S i+1 ,则称 S i 和 S i+1 为边缘
字符。如果 S i , S i?1 且 S i = S i+1,则 S i?1 和 S i 也称为边缘字符。其它的字符
都不是边缘字符。
对于一个给定的串 S,一次操作可以一次性删除该串中的所有边缘字符
(操作后可能产生新的边缘字符)。
请问经过 2
64 次操作后,字符串 S 变成了怎样的字符串,如果结果为空则
输出 EMPTY。
【输入格式】
输入一行包含一个字符串 S 。
【输出格式】
输出一行包含一个字符串表示答案,如果结果为空则输出 EMPTY。
【样例输入 1】
edda
【样例输出 1】
EMPTY
【样例输入 2】
sdfhhhhcvhhxcxnnnnshh
【样例输出 2】
s
试题 F: 消除游戏 9
第十三届蓝桥杯大赛软件赛省赛 Python 大学 B 组
【评测用例规模与约定】
对于 25% 的评测用例,|S | ≤ 103 ,其中 |S | 表示 S 的长度;
对于 50% 的评测用例,|S | ≤ 104

对于 75% 的评测用例,|S | ≤ 105 ;
对于所有评测用例,|S | ≤ 106,S 中仅含小写字母。
试题 F: 消除游戏 10
第十三届蓝桥杯大赛软件赛省赛 Python 大学 B 组
试题 G: 全排列的价值
时间限制: 1.0s 内存限制: 512.0MB 本题总分:20 分
【问题描述】
对于一个排列 A = (a1, a2, · · · , an),定义价值 ci 为 a1 至 ai?1 中小于 ai 的数
的个数,即 bi = |{aj
| j < i, aj < ai}|。定义 A 的价值为 ∑n
i=1 ci。
给定 n,求 1 至 n 的全排列中所有排列的价值之和。
【输入格式】
输入一行包含一个整数 n 。
【输出格式】
输出一行包含一个整数表示答案,由于所有排列的价值之和可能很大,请
输出这个数除以 998244353 的余数。
【样例输入 1】
3
【样例输出 1】
9
【样例输入 2】
2022
【样例输出 2】
593300958
【样例说明】
1 至 3 构成的所有排列的价值如下:
试题 G: 全排列的价值 11
第十三届蓝桥杯大赛软件赛省赛 Python 大学 B 组
(1, 2, 3) : 0 + 1 + 2 = 3 ;
(1, 3, 2) : 0 + 1 + 1 = 2 ;
(2, 1, 3) : 0 + 0 + 2 = 2 ;
(2, 3, 1) : 0 + 1 + 0 = 1 ;
(3, 1, 2) : 0 + 0 + 1 = 1 ;
(3, 2, 1) : 0 + 0 + 0 = 0 ;
故总和为 3 + 2 + 2 + 1 + 1 = 9。
【评测用例规模与约定】
对于 40% 的评测用例,n ≤ 20 ;
对于 70% 的评测用例,n ≤ 5000 ;
对于所有评测用例,2 ≤ n ≤ 106 。
试题 G: 全排列的价值 12
第十三届蓝桥杯大赛软件赛省赛 Python 大学 B 组
试题 H: 技能升级
时间限制: 1.0s 内存限制: 512.0MB 本题总分:20 分
【问题描述】
小蓝最近正在玩一款 RPG 游戏。他的角色一共有 N 个可以加攻击力的技
能。其中第 i 个技能首次升级可以提升 Ai 点攻击力,以后每次升级增加的点数
都会减少 Bi。?
Ai
Bi
? (上取整) 次之后,再升级该技能将不会改变攻击力。
现在小蓝可以总计升级 M 次技能,他可以任意选择升级的技能和次数。请
你计算小蓝最多可以提高多少点攻击力?
【输入格式】
输入第一行包含两个整数 N 和 M。
以下 N 行每行包含两个整数 Ai 和 Bi。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
3 6
10 5
9 2
8 1
【样例输出】
47
【评测用例规模与约定】
对于 40% 的评测用例,1 ≤ N, M ≤ 1000;
试题 H: 技能升级 13
第十三届蓝桥杯大赛软件赛省赛 Python 大学 B 组
对于 60% 的评测用例,1 ≤ N ≤ 104
, 1 ≤ M ≤ 107;
对于所有评测用例,1 ≤ N ≤ 105,1 ≤ M ≤ 2 × 109,1 ≤ Ai
, Bi ≤ 106。
试题 H: 技能升级 14
第十三届蓝桥杯大赛软件赛省赛 Python 大学 B 组
试题 I: 最长不下降子序列
时间限制: 1.0s 内存限制: 512.0MB 本题总分:25 分
【问题描述】
给定一个长度为 N 的整数序列:A1, A2, · · · , AN。现在你有一次机会,将其
中连续的 K 个数修改成任意一个相同值。请你计算如何修改可以使修改后的数
列的最长不下降子序列最长,请输出这个最长的长度。
最长不下降子序列是指序列中的一个子序列,子序列中的每个数不小于在
它之前的数。
【输入格式】
输入第一行包含两个整数 N 和 K。
第二行包含 N 个整数 A1, A2, · · · , AN。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
5 1
1 4 2 8 5
【样例输出】
4
【评测用例规模与约定】
对于 20% 的评测用例,1 ≤ K ≤ N ≤ 100;
对于 30% 的评测用例,1 ≤ K ≤ N ≤ 1000;
试题 I: 最长不下降子序列 15
第十三届蓝桥杯大赛软件赛省赛 Python 大学 B 组
对于 50% 的评测用例,1 ≤ K ≤ N ≤ 10000;
对于所有评测用例,1 ≤ K ≤ N ≤ 105,1 ≤ Ai ≤ 106。
试题 I: 最长不下降子序列 16
第十三届蓝桥杯大赛软件赛省赛 Python 大学 B 组
试题 J: 最优清零方案
时间限制: 5.0s 内存限制: 512.0MB 本题总分:25 分
【问题描述】
给定一个长度为 N 的数列 A1, A2, · · · , AN。现在小蓝想通过若干次操作将
这个数列中每个数字清零。
每次操作小蓝可以选择以下两种之一:

  1. 选择一个大于 0 的整数,将它减去 1;
  2. 选择连续 K 个大于 0 的整数,将它们各减去 1。
    小蓝最少经过几次操作可以将整个数列清零?
    【输入格式】
    输入第一行包含两个整数 N 和 K。
    第二行包含 N 个整数 A1, A2, · · · , AN。
    【输出格式】
    输出一个整数表示答案。
    【样例输入】
    4 2
    1 2 3 4
    【样例输出】
    6
    【评测用例规模与约定】
    对于 20% 的评测用例,1 ≤ K ≤ N ≤ 10。
    试题 J: 最优清零方案 17
    第十三届蓝桥杯大赛软件赛省赛 Python 大学 B 组
    对于 40% 的评测用例,1 ≤ K ≤ N ≤ 100。
    对于 50% 的评测用例,1 ≤ K ≤ N ≤ 1000。
    对于 60% 的评测用例,1 ≤ K ≤ N ≤ 10000。
    对于 70% 的评测用例,1 ≤ K ≤ N ≤ 100000。
    对于所有评测用例,1 ≤ K ≤ N ≤ 1000000, 0 ≤ Ai ≤ 1000000。
    试题 J: 最优清零方案 18

    推荐阅读