也可在
https://download.csdn.net/download/weixin_43960044/85099211
地址下载。
侵权删
试题 A: 排列字母
本题总分：5 分
【问题描述】
小蓝要把一个字符串中的字母按其在字母表中的顺序排列。
例如，LANQIAO 排列后为 AAILNOQ。
又如，GOODGOODSTUDYDAYDAYUP 排列后为AADDDDDGGOOOOPSTUUYYY。
请问对于以下字符串，排列之后字符串是什么？
WHERETHEREISAWILLTHEREISAWAY
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个由大写字母组成的字符串，在提交答案时只填写这个字符串，填写多余的内容将无法得分
试题 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
≤ 10^9。
对于所有评测用例，1 ≤
n
≤ 10^16。
试题
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。
试题
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-FIQcaDOK-1649486699622)(C:\Users\gzc\AppData\Roaming\Typora\typora-user-images\1649485880395.png)]
给定点 (
d
1,
p
1,
q
1) 和点 (
d
2,
p
2,
q
2)，请问他们之间最少走多少步可以到达？
【输入格式】
输入一行包含 6 个整数
d
1,
p
1,
q
1,
d
2,
p
2,
q
2 表示两个点的坐标，相邻两个整
数之间使用一个空格分隔。
【输出格式】
输出一行包含一个整数表示两点之间最少走多少步可以到达。
【样例输入】
0 5 3 2 3 2
【样例输出】
7
【评测用例规模与约定】
对于 25% 的评测用例，
p
1,
p
2 ≤ 10^3 ；
对于 50% 的评测用例，
p
1,
p
2 ≤ 10^5 ；
对于 75% 的评测用例，
p
1,
p
2 ≤ 10^7 ；
对于所有评测用例，0 ≤
d
1,
d
2 ≤ 5，0 ≤
q
1 <
p
1 ≤ 10^9，0 ≤
q
2 <
p
2 ≤ 10^9 。
试题
F:
爬树的甲壳虫
时间限制: 1.0s
内存限制: 512.0MB
本题总分：15 分
【问题描述】
有一只甲壳虫想要爬上一颗高度为
n
的树，它一开始位于树根，高度为 0， 当它尝试从高度
i
− 1 爬到高度为
i
的位置时有
P**i
的概率会掉回树根，求它从树根爬到树顶时，经过的时间的期望值是多少。
【输入格式】
输入第一行包含一个整数
n
表示树的高度。
接下来
n
行每行包含两个整数
xi
,
yi
，用一个空格分隔，表示
Pi
= xi / yi。
【输出格式】
输出一行包含一个整数表示答案，答案是一个有理数，请输出答案对质 数 998244353 取模的结果。其中有理数
a
b
对质数
P
取模的结果是整数
c
满足 0 ≤
c
<
P
且
c
·
b
≡
a
(mod
P
)。
【样例输入 1】
1
1 2
【样例输出 1】
2
【样例输入 2】
3
1 2
3 5
7 11
【样例输出 2】
623902744
【评测用例规模与约定】
对于 20% 的评测用例，
n
≤ 2，1 ≤
x**i
<
y**i
≤ 20 ；
对于 50% 的评测用例，
n
≤ 500，1 ≤
x**i
<
y**i
≤ 200 ；
对于所有评测用例，1 ≤
n
≤ 100000，1 ≤
x**i
<
y**i
≤ 10^9 。
试题
G:
重新排序
时间限制: 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
【样例说明】
原来的和为 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 。
试题
H:
技能升级
时间限制: 1.0s
内存限制: 512.0MB
本题总分：20 分
【问题描述】
小蓝最近正在玩一款 RPG 游戏。他的角色一共有
N
个可以加攻击力的技 能。其中第
i
个技能首次升级可以提升
Ai
点攻击力，以后每次升级增加的点数都会减少
Bi
。⌈ Ai/Bi⌉ (上取整) 次之后，再升级该技能将不会改变攻击力。
现在小蓝可以总计升级
M
次技能，他可以任意选择升级的技能和次数。请 你计算小蓝最多可以提高多少点攻击力？
【输入格式】
输入第一行包含两个整数
N
和
M
。
以下
N
行每行包含两个整数
A**i
和
B**i
。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
3 6
10 5
9 2
8 1
【样例输出】
47
【评测用例规模与约定】
对于 40% 的评测用例，1 ≤
N
,
M
≤ 1000；
对于 60% 的评测用例，1 ≤
N
≤ 10^4, 1 ≤
M
≤ 10^7；
对于所有评测用例，1 ≤
N
≤ 10^5，1 ≤
M
≤ 2 × 10^9，1 ≤
A**i
,
B**i
≤ 10^6。
试题
I:
最优清零方案
时间限制: 3.0s
内存限制: 512.0MB
本题总分：25 分
【问题描述】
给定一个长度为
N
的数列
A
1,
A
2, · · · ,
AN
。现在小蓝想通过若干次操作将 这个数列中每个数字清零。
每次操作小蓝可以选择以下两种之一：
-
选择一个大于 0 的整数，将它减去 1；
-
选择连续
K
个大于 0 的整数，将它们各减去 1。
小蓝最少经过几次操作可以将整个数列清零？
【输入格式】
输入第一行包含两个整数
N
和
K
。
第二行包含
N
个整数
A
1,
A
2, · · · ,
AN
。
【输出格式】
输出一个整数表示答案。
【样例输入】
4 2
1 2 3 4
【样例输出】
6
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤
K
≤
N
≤ 10
对于 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:
推导部分和
时间限制: 1.0s
内存限制: 512.0MB
本题总分：25 分
【问题描述】
对于一个长度为
N
的整数数列
A
1,
A
2, · · ·
AN
，小蓝想知道下标 l 到
r
的部分和 是多少？
然而，小蓝并不知道数列中每个数的值是多少，他只知道它的 M个部分和 的值。其中第
i
个部分和是下标
li
到
ri
的部分和的值是
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
UNKNOWN
【评测用例规模与约定】
对于 10% 的评测用例，1 ≤
N
,
M
,
Q
≤ 10，−100 ≤
S
i
≤ 100。
对于 20% 的评测用例，1 ≤
N
,
M
,
Q
≤ 20，−1000 ≤
S
i
≤ 1000。
对于 30% 的评测用例，1 ≤
N
,
M
,
Q
≤ 50，−10000 ≤
S
i
≤ 10000。
对于 40% 的评测用例，1 ≤
N
,
M
,
Q
≤ 1000，−10^6 ≤
S
i
≤ 10^6。
对于 60% 的评测用例，1 ≤
N
,
M
,
Q
≤ 10000，−10^9 ≤
S
i
≤ 10^9。
对于所有评测用例，1 ≤
N
,
M
,
Q
≤ 10
5，−10
12 ≤
S
i
≤ 10^12，1 ≤
li
≤
ri
≤
N
，
1 ≤
l
≤
r
≤
N
。数据保证没有矛盾。