第十三届蓝桥杯大赛软件赛省赛 Java 研究生组

【考生须知】

考试开始后，选手首先下载题目，并使用考场现场公布的解压密码解压试 题。

考试时间为 4 小时。考试期间选手可浏览自己已经提交的答案，被浏览的 答案允许拷贝。时间截止后，将无法继续提交或浏览答案。 对同一题目，选手可多次提交答案，以最后一次提交的答案为准。

选手必须通过浏览器方式提交自己的答案。选手在其它位置的作答或其它 方式提交的答案无效。 试题包含“结果填空”和“程序设计”两种题型。 结果填空题：要求选手根据题目描述直接填写结果。求解方式不限。

不要 求源代码。把结果填空的答案直接通过 页提交即可，不要书写多余的内容。 程序设计题：要求选手设计的程序对于给定的输入能给出正确的输出结果。 考生的程序只有能运行出正确结果才有机会得分。

注意：在评卷时使用的输入数据与试卷中给出的示例数据可能是不同的。 选手的程序必须是通用的，不能只对试卷中给定的数据有效。 所有源码必须在同一文件中。调试通过后，拷贝提交。

注意：不要使用 package 语句。 注意：选手代码的主类名必须为：Main，否则会被判为无效代码。 注意：如果程序中引用了类库，在提交时必须将 import 语句与程序的其 他部分同时提交。只允许使用 Java 自带的类库。

试题 A: 排列字母

本题总分：5 分

【问题描述】

小蓝要把一个字符串中的字母按其在字母表中的顺序排列。

例如，LANQIAO 排列后为 AAILNOQ。 又如，GOODGOODSTUDYDAYDAYUP 排列后为 AADDDDDGGOOOOPSTUUYYY 。

请问对于以下字符串，排列之后字符串是什么HERETHEREISAWILLTHEREISAWAY

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个由大写字母组成的字符串，在提交答案时只填写这个字符串，填写多余的内 容将无法得分

试题 B: 灭鼠先锋

本题总分：5 分

【问题描述】

灭鼠先锋是一个老少咸宜的棋盘小游戏，由两人参与，轮流操作。 灭鼠先锋的棋盘有各种规格，本题中游戏在两行四列的棋盘上进行。游戏 的规则为：两人轮流操作，每次可选择在棋盘的一个空位上放置一个棋子，或 在同一行的连续两个空位上各放置一个棋子，放下棋子后使棋盘放满的一方输 掉游戏。 小蓝和小乔一起玩游戏，小蓝先手，小乔后手。小蓝可以放置棋子的方法 很多，通过旋转和翻转可以对应如下四种情况： XOOO XXOO OXOO OXXO OOOO OOOO OOOO OOOO 其中 O 表示棋盘上的一个方格为空，X 表示该方格已经放置了棋子。 请问，对于以上四种情况，如果小蓝和小乔都是按照对自己最优的策略来 玩游戏，小蓝是否能获胜。如果获胜，请用 V 表示，否则用 L 表示。请将四种 情况的胜负结果按顺序连接在一起提交。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个长度为 4 的由大写字母 V 和 L 组成的字符串，如 VVLL，在提交答案时只填 写这个字符串，填写多余的内容将无法得分。

试题 C: 质因数个数

时间限制: 5.0s 内存限制: 512.0MB 本题总分：10 分

【问题描述】

给定正整数 n，请问有多少个质数是 n 的约数。

【输入格式】

输入的第一行包含一个整数 n。

【输出格式】

输出一个整数，表示 n 的质数约数个数。

【样例输入】

396

【样例输出】 3

【样例说明】

396 有 2, 3, 11 三个质数约数。

【评测用例规模与约定】

对于 30% 的评测用例，1 ≤ n ≤ 10000。 对于 60% 的评测用例，1 ≤ n ≤ 109。 对于所有评测用例，1 ≤ n ≤ 1016。

试题 D: 数位排序

时间限制: 1.0s 内存限制: 512.0MB 本题总分：10 分

【问题描述】

小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。当 两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时， 将数值小的排在前面。 例如，2022 排在 409 前面，因为 2022 的数位之和是 6，小于 409 的数位 之和 13。 又如，6 排在 2022 前面，因为它们的数位之和相同，而 6 小于 2022。 给定正整数 n，m，请问对 1 到 n 采用这种方法排序时，排在第 m 个的元 素是多少p>

【输入格式】 输入第一行包含一个正整数 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。

试题 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) 的示意。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dnJoXH7h-1650161501064)(C:UsersPengAppDataRoamingTyporatypora-user-imagesimage-20220417100726910.png)]

给定点 (d1, p1, q1) 和点 (d2, p2, q2)，请问他们之间最少走多少步可以到达p>

【输入格式】 输入一行包含 6 个整数 d1, p1, q1, d2, p2, q2 表示两个点的坐标，相邻两个整 数之间使用一个空格分隔。

【输出格式】 输出一行包含一个整数表示两点之间最少走多少步可以到达。

【样例输入】 0 5 3 2 3 2

【样例输出】 7

试题 F: 爬树的甲壳虫

时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分

【问题描述】

有一只甲壳虫想要爬上一颗高度为 n 的树，它一开始位于树根，高度为 0， 当它尝试从高度 i ? 1 爬到高度为 i 的位置时有 Pi 的概率会掉回树根，求它从 树根爬到树顶时，经过的时间的期望值是多少。

【输入格式】

输入第一行包含一个整数 n 表示树的高度。 接下来 n 行每行包含两个整数 xi , yi，用一个空格分隔，表示 Pi = xi yi。

【输出格式】

输出一行包含一个整数表示答案，答案是一个有理数，请输出答案对质 数 998244353 取模的结果。其中有理数 a b 对质数 P 取模的结果是整数 c 满足 0 ≤ c

【样例输入 1】

1

1 2

【样例输出 1】

2

【样例输入 2】

3

1 2

3 5

7 11

【样例输出 2】

623902744

试题 G: 重新排序

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分

【问题描述】

给定一个数组 A 和一些查询 Li , Ri，求数组中第 Li 至第 Ri 个元素之和。 小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查 询结果的和尽可能地大。小蓝想知道相比原数组，所有查询结果的总和最多可 以增加多少p>

【输入格式】

输入第一行包含一个整数 n。 第二行包含 n 个整数 A1, A2, · · · , An，相邻两个整数之间用一个空格分隔。 第三行包含一个整数 m 表示查询的数目。 接下来 m 行，每行包含两个整数 Li、Ri ，相邻两个整数之间用一个空格分 隔。 【输出格式】

输出一行包含一个整数表示答案。

【样例输入】

5

1 2 3 4 5

2

1 3

2 5

【样例输出】

4

【样例说明】 原来的和为 6 + 14 = 20，重新排列为 (1, 4, 5, 2, 3) 后和为 10 + 14 = 24，增 加了 4

试题 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

试题 I: 最优清零方案

时间限制: 3.0s 内存限制: 512.0MB 本题总分：25 分

【问题描述】

给定一个长度为 N 的数列 A1, A2, · · · , AN。现在小蓝想通过若干次操作将 这个数列中每个数字清零。 每次操作小蓝可以选择以下两种之一： 1. 选择一个大于 0 的整数，将它减去 1； 2. 选择连续 K 个大于 0 的整数，将它们各减去 1。 小蓝最少经过几次操作可以将整个数列清零p>

【输入格式】 输入第一行包含两个整数 N 和 K。 第二行包含 N 个整数 A1, A2, · · · , AN。

【输出格式】 输出一个整数表示答案。

【样例输入】

4 2

1 2 3 4

【样例输出】 6

试题 J: 推导部分和

时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分

【问题描述】

对于一个长度为 N 的整数数列 A1, A2, · · · AN，小蓝想知道下标 l 到 r 的部 分和 ∑r i=l = Al + Al+1 + · · · + Ar 是多少而，小蓝并不知道数列中每个数的值是多少，他只知道它的 M 个部分和 的值。其中第 i 个部分和是下标 li 到 ri 的部分和 ∑ri j=li = Ali + Ali+1 + · · · + Ari ， 值是 S i。

【输入格式】 第一行包含 3 个整数 N、M 和 Q。分别代表数组长度、已知的部分和数量 和询问的部分和数量。 接下来 M 行，每行包含 3 个整数 li ,ri , S i。 接下来 Q 行，每行包含 2 个整数 l 和 r ，代表一个小蓝想知道的部分和。 【输出格式】 对于每个询问，输出一行包含一个整数表示答案。如果答案无法确定，输 出 UNKNOWN。

【样例输入】

5 3 3

1 5 15

4 5 9

2 3 5

1 5

1 3

1 2

【样例输出】

15 6

格式】 第一行包含 3 个整数 N、M 和 Q。分别代表数组长度、已知的部分和数量 和询问的部分和数量。 接下来 M 行，每行包含 3 个整数 li ,ri , S i。 接下来 Q 行，每行包含 2 个整数 l 和 r ，代表一个小蓝想知道的部分和。 【输出格式】 对于每个询问，输出一行包含一个整数表示答案。如果答案无法确定，输 出 UNKNOWN。

【样例输入】

5 3 3

1 5 15

4 5 9

2 3 5

1 5

1 3

1 2

【样例输出】

15 6

UNKNOWN

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览35192 人正在系统学习中