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

试题 A: 排列字母

本题总分： 5 分
【问题描述】
小蓝要把一个字符串中的字母按其在字母表中的顺序排列。
例如， LANQIAO 排列后为 AAILNOQ 。
又如， GOODGOODSTUDYDAYDAYUP 排列后为 AADDDDDGGOOOOPSTUUYYY
。
请问对于以下字符串，排列之后字符串是什么？
WHERETHEREISAWILLTHEREISAWAY
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个由大写字母组成的字符串，在提交答案时只填写这个字符串，填写多余的内
容将无法得分

试题 B: 特殊时间

本题总分： 5 分
【问题描述】
2022 年 2 月 22 日 22:20 是一个很有意义的时间，年份为 2022 ，由 3 个 2
和 1 个 0 组成，如果将月和日写成 4 位，为 0222 ，也是由 3 个 2 和 1 个 0 组
成，如果将时间中的时和分写成 4 位，还是由 3 个 2 和 1 个 0 组成。
小蓝对这样的时间很感兴趣，他还找到了其它类似的例子，比如 111 年 10
月 11 日 01:11 ， 2202 年 2 月 22 日 22:02 等等。
请问，总共有多少个时间是这种年份写成 4 位、月日写成 4 位、时间写成
4 位后由 3 个一种数字和 1 个另一种数字组成。注意 1111 年 11 月 11 日 11:11
不算，因为它里面没有两种数字。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

试题 C: 纸张尺寸

时间限制 : 1.0s
内存限制 : 512.0MB
本题总分： 10 分
【问题描述】
在 ISO 国际标准中定义了 A0 纸张的大小为 1189 mm × 841 mm ，将 A0 纸
沿长边对折后为 A1 纸，大小为 841 mm × 594 mm ，在对折的过程中长度直接取
下整（实际裁剪时可能有损耗）。将 A1 纸沿长边对折后为 A2 纸，依此类推。
输入纸张的名称，请输出纸张的大小。
【输入格式】
输入一行包含一个字符串表示纸张的名称，该名称一定是 A0 、 A1 、 A2 、
A3 、 A4 、 A5 、 A6 、 A7 、 A8 、 A9 之一。
【输出格式】
输出两行，每行包含一个整数，依次表示长边和短边的长度。
【样例输入 1 】
A0
【样例输出 1 】
1189
841
【样例输入 2 】
A1
【样例输出 2 】
841
594

试题 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
【样例说明】
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 ≤ 10 6

试题 F: GCD

时间限制 : 1.0s
内存限制 : 512.0MB
本题总分： 15 分
【问题描述】
给定两个不同的正整数 a , b ，求一个正整数 k 使得 gcd ( a + k , b + k ) 尽可能
大，其中 gcd ( a , b ) 表示 a 和 b 的最大公约数，如果存在多个 k ，请输出所有满
足条件的 k 中最小的那个。
【输入格式】
输入一行包含两个正整数 a , b ，用一个空格分隔。
【输出格式】
输出一行包含一个正整数 k 。
【样例输入】
5 7
【样例输出】
1
【评测用例规模与约定】
对于 20 % 的评测用例， a < b ≤ 10 5 ；
对于 40 % 的评测用例， a < b ≤ 10 9 ；
对于所有评测用例， 1 ≤ a < b ≤ 10 18 。

试题 G: 蜂巢

时间限制 : 1.0s
内存限制 : 512.0MB

试题 H: 重新排序

时间限制 : 1.0s
内存限制 : 512.0MB
本题总分： 20 分
【问题描述】
给定一个数组 A 和一些查询 L i , R i ，求数组中第 L i 至第 R i 个元素之和。
小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查
询结果的和尽可能地大。小蓝想知道相比原数组，所有查询结果的总和最多可
以增加多少 ?
【输入格式】
输入第一行包含一个整数 n 。
第二行包含 n 个整数 A 1 , A 2 , · · · , A n ，相邻两个整数之间用一个空格分隔。
第三行包含一个整数 m 表示查询的数目。
接下来 m 行，每行包含两个整数 L i 、 R i ，相邻两个整数之间用一个空格分
隔。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
5
1 2 3 4 5
2
1 3
2 5
【样例输出】
4
试题 H: 重新排序
12 第十三届蓝桥杯大赛软件赛省赛 Python 大学 C 组
【样例说明】
原来的和为 6 + 14 = 20 ，重新排列为 (1 , 4 , 5 , 2 , 3) 后和为 10 + 14 = 24 ，增
加了 4 。
【评测用例规模与约定】
对于 30 % 的评测用例， n , m ≤ 50 ；
对于 50 % 的评测用例， n , m ≤ 500 ；
对于 70 % 的评测用例， n , m ≤ 5000 ；
对于所有评测用例， 1 ≤ n , m ≤ 10 5 ， 1 ≤ A i ≤ 10 6 ， 1 ≤ L i ≤ R i ≤ 10 6 。

试题 I: 青蛙过河

时间限制 : 1.0s
内存限制 : 512.0MB
本题总分： 25 分
【问题描述】
小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里
的石头跳到对岸。
河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。
不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就
会下降 1 ，当石头的高度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃
后使石头高度下降到 0 是允许的）。
小青蛙一共需要去学校上 x 天课，所以它需要往返 2 x 次。当小青蛙具有
一个跳跃能力 y 时，它能跳不超过 y 的距离。
请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。
【输入格式】
输入的第一行包含两个整数 n , x ，分别表示河的宽度和小青蛙需要去学校
的天数。请注意 2 x 才是实际过河的次数。
第二行包含 n ? 1 个非负整数 H 1 , H 2 , · · · , H n ? 1 ，其中 H i > 0 表示在河中与
小青蛙的家相距 i 的地方有一块高度为 H i 的石头， H i = 0 表示这个位置没有石
头。
【输出格式】
输出一行，包含一个整数，表示小青蛙需要的最低跳跃能力。
【样例输入】
5 1
1 0 1 0
试题 I: 青蛙过河
14 第十三届蓝桥杯大赛软件赛省赛 Python 大学 C 组
【样例输出】
4
【样例解释】
由于只有两块高度为 1 的石头，所以往返只能各用一块。第 1 块石头和对
岸的距离为 4 ，如果小青蛙的跳跃能力为 3 则无法满足要求。所以小青蛙最少
需要 4 的跳跃能力。
【评测用例规模与约定】
对于 30 % 的评测用例， n ≤ 100 ；
对于 60 % 的评测用例， n ≤ 1000 ；
对于所有评测用例，1 ≤ n ≤ 10 5 , 1 ≤ x ≤ 10 9 , 1 ≤ H i ≤ 10 4 。