发现宝藏

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。【宝藏入口】。

---

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

---

【考生须知】

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

考试时间为 4 小时。考试期间选手可浏览自己已经提交的答案, 被浏览的答案允许拷贝。时间截止后，将无法继续提交或浏览答案。

对同一题目, 选手可多次提交答案, 以最后一次提交的答案为准。

选手必须通过浏览器方式提交自己的答案。选手在其它位置的作答或其它方式提交的答案无效。

试题包含 “结果填空” 和 “程序设计” 两种题型。

结果填空题: 要求选手根据题目描述直接填写结果。求解方式不限。不要求源代码。把结果填空的答案直接通过网页提交即可, 不要书写多余的内容。

程序设计题: 要求选手设计的程序对于给定的输入能给出正确的输出结果。考生的程序只有能运行出正确结果才有机会得分。

注意: 在评卷时使用的输入数据与试卷中给出的示例数据可能是不同的。选手的程序必须是通用的, 不能只对试卷中给定的数据有效。

所有源码必须在同一文件中。调试通过后，拷贝提交。

注意: 不要使用 package 语句。

注意：选手代码的主类名必须为: Main, 否则会被判为无效代码。

注意: 如果程序中引用了类库, 在提交时必须将 import 语句与程序的其他部分同时提交。只允许使用 Java 自带的类库。

---

试题 A: 排列字母

本题总分: 5 分

【问题描述】

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

例如, LANQIAO 排列后为 AAILNOQ。

又如, GOODGOODSTUDYDAYDAYUP 排列后为 AADDDDDGGOOOOPSTUUYYY

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

WHERETHEREISAWILLTHEREISAWAY

【答案提交】

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

---

试题 B: 灭鼠先锋

本题总分: 5 分

【问题描述】

灭鼠先锋是一个老少咸宜的棋盘小游戏, 由两人参与, 轮流操作。

灭鼠先锋的棋盘有各种规格, 本题中游戏在两行四列的棋盘上进行。游戏的规则为: 两人轮流操作, 每次可选择在棋盘的一个空位上放置一个棋子, 或在同一行的连续两个空位上各放置一个棋子, 放下棋子后使棋盘放满的一方输掉游戏。

小蓝和小乔一起玩游戏, 小蓝先手, 小乔后手。小蓝可以放置棋子的方法很多, 通过旋转和翻转可以对应如下四种情况:

其中 0 表示棋盘上的一个方格为空， $\mathrm{x}$ 表示该方格已经放置了棋子。

请问, 对于以上四种情况, 如果小蓝和小乔都是按照对自己最优的策略来玩游戏, 小蓝是否能获胜。如果获胜, 请用 $\mathrm{V}$ 表示, 否则用 $\mathrm{L}$ 表示。请将四种情况的胜负结果挍顺序连接在一起提交。

【答案提交】

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

---

试题 C: 质因数个数

时间限制: $5.0\mathrm{s}$ 内存限制: $512.0\mathrm{MB}$ 本题总分: 10 分

【问题描述】

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

【输入格式】

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

【输出格式】

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

【样例输入】

$\begin{array}{l}396\end{array}$

【样例输出】

$\begin{array}{l}3\end{array}$

【样例说明】

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

【评测用例规模与约定】

对于 $30\%$ 的评测用例, $1\le n\le 10000$ 。

对于 $60\%$ 的评测用例, $1\le n\le 10^9$ 。

对于所有评测用例, $1\le n\le 10^{16}$ 。

---

试题 D: 数位排序

时间限制: $1.0\mathrm{s}$ 内存限制: $512.0\mathrm{MB}$ 本题总分： 10 分

【问题描述】

小蓝对一个数的数位之和很感兴趣, 今天他要按照数位之和给数排序。当两个数各个数位之和不同时, 将数位和较小的排在前面, 当数位之和相等时,将数值小的排在前面。

例如, 2022 排在 409 前面, 因为 2022 的数位之和是 6 , 小于 409 的数位之和 13 。

又如, 6 排在 2022 前面, 因为它们的数位之和相同, 而 6 小于 2022 。

给定正整数 $n,m$, 请问对 1 到 $n$ 采用这种方法排序时，排在第 $m$ 个的元素是多少?

【输入格式】

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

第二行包含一个正整数 $m$ 。

【输出格式】

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

【样例输入】

$\begin{array}{l}13\end{array}$

$\begin{array}{l}5\end{array}$

【样例输出】

$\begin{array}{l}3\end{array}$

【样例说明】

1 到 13 的排序为: $1,10,2,11,3,12,4,13,5,6,7,8,9$ 。第 5 个数为 3 。

【评测用例规模与约定】

对于 $30\%$ 的评测用例, $1\le m\le n\le 300$ 。

对于 $50\%$ 的评测用例， $1\le m\le n\le 1000$ 。

对于所有评测用例， $1\le m\le n\le 10^6$ 。

---

试题 E: 蜂巢

时间限制: $1.0\mathrm{s}$ 内存限制: $512.0\mathrm{MB}$ 本题总分: 15 分

【问题描述】

蜂巢由大量的六边形拼接而成, 定义蜂巢中的方向为: 0 表示正西方向, 1 表示西偏北 $60^{\circ },2$ 表示东偏北 $60^{\circ },3$ 表示正东, 4 表示东偏南 $60^{\circ },5$ 表示西偏南 $60^{\circ }$ 。

对于给定的一点 $O$, 我们以 $O$ 为原点定义坐标系, 如果一个点 $A$ 由 $O$ 点先向 $d$ 方向走 $p$ 步再向 $(d+2)\mathrm{mod}6$ 方向 ( $d$ 的顺时针 $120^{\circ }$ 方向) 走 $q$ 步到达, 则这个点的坐标定义为 $(d,p,q)$ 。在蜂窝中, 一个点的坐标可能有多种。

下图给出了点 $B(0,5,3)$ 和点 $C(2,3,2)$ 的示意。

给定点 $\left(d_1,p_1,q_1\right)$ 和点 $\left(d_2,p_2,q_2\right)$, 请问他们之间最少走多少步可以到达?

【输入格式】

输入一行包含 6 个整数 $d_1,p_1,q_1,d_2,p_2,q_2$ 表示两个点的坐标, 相邻两个整数之间使用一个空格分隔。

【输出格式】

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

【样例输入】

$\begin{array}{llllll}0& 5& 3& 2& 3& 2\end{array}$

【样例输出】

$\begin{array}{l}7\end{array}$

【评测用例规模与约定】

对于 $25\%$ 的评测用例, $p_1,p_2\le 10^3$;

对于 $50\%$ 的评测用例, $p_1,p_2\le 10^5$;

对于 $75\%$ 的评测用例, $p_1,p_2\le 10^7$;

对于所有评测用例, $0\le d_1,d_2\le 5,0\le q_1<p_1\le 10^9,0\le q_2<p_2\le 10^9$ 。

---

试题 $\mathrm{F}:$ 爬树的甲壳虫

时间限制: $1.0\mathrm{s}$ 内存限制: $512.0\mathrm{MB}$ 本题总分: 15 分

【问题描述】

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

【输入格式】

输入第一行包含一个整数 $n$ 表示树的高度。

接下来 $n$ 行每行包含两个整数 $x_i,y_i$, 用一个空格分隔, 表示 $P_i=\frac{x_i}{y_i}$ 。

【输出格式】

输出一行包含一个整数表示答案, 答案是一个有理数, 请输出答案对质数 998244353 取模的结果。其中有理数 $\frac{a}{b}$ 对质数 $P$ 取模的结果是整数 $c$ 满足 $0\le c<P$ 且 $c\cdot b\equiv a(\mathrm{mod}P)$ 。

【样例输入 1】

$\begin{array}{l}1\end{array}$

$\begin{array}{ll}1& 2\end{array}$

【样例输出 1】

$\begin{array}{l}2\end{array}$

【样例输入 2】

$\begin{array}{l}3\end{array}$

$\begin{array}{ll}1& 2\end{array}$

$\begin{array}{ll}3& 5\end{array}$

$\begin{array}{ll}7& 11\end{array}$

【样例输出 2】

$\begin{array}{l}623902744\end{array}$

【评测用例规模与约定】

对于 $20\%$ 的评测用例, $n\le 2,1\le x_i<y_i\le 20$ ，

对于 $50\%$ 的评测用例, $n\le 500,1\le x_i<y_i\le 200$ ；

对于所有评测用例, $1\le n\le 100000,1\le x_i<y_i\le 10^9$ 。

---

试题 G: 重新排序

时间限制: $1.0\mathrm{s}$ 内存限制: $512.0\mathrm{MB}$ 本题总分: 20 分

【问题描述】

给定一个数组 $A$ 和一些查询 $L_i,R_i$, 求数组中第 $L_i$ 至第 $R_i$ 个元素之和。

小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可以增加多少?

【输入格式】

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

第二行包含 $n$ 个整数 $A_1,A_2,\cdots ,A_n$, 相邻两个整数之间用一个空格分隔。

第三行包含一个整数 $m$ 表示查论的数目。

接下来 $m$ 行, 每行包含两个整数 $L_i、R_i$, 相邻两个整数之间用一个空格分谝。

【输出格式】

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

【样例输入】

$\begin{array}{l}5\end{array}$

$\begin{array}{lllll}1& 2& 3& 4& 5\end{array}$

$\begin{array}{l}2\end{array}$

$\begin{array}{ll}1& 3\end{array}$

$\begin{array}{ll}2& 5\end{array}$

【样例输出】

$\begin{array}{l}4\end{array}$

【样例说明】

原来的和为 $6+14=20$, 重新排列为 $(1,4,5,2,3)$ 后和为 $10+14=24$, 增加了 4 。

【评测用例规模与约定】

对于 $30\%$ 的评测用例, $n,m\le 50$ ；

对于 $50\%$ 的评测用例, $n,m\le 500$ ；

对于 $70\%$ 的评测用例, $n,m\le 5000$ ，

对于所有评测用例, $1\le n,m\le 10^5,1\le A_i\le 10^6,1\le L_i\le R_i\le 10^6$ 。

---

试题 $\mathrm{H}$ : 技能升级

时间限制: $1.0\mathrm{s}$ 内存限制: $512.0\mathrm{MB}$ 本题总分: 20 分

【问题描述】

小蓝最近正在玩一款 RPG 游戏。他的角色一共有 $N$ 个可以加攻击力的技能。其中第 $i$ 个技能首次升级可以提升 $A_i$ 点攻击力, 以后每次升级增加的点数都会减少 $B_i$ 。$\lceil \frac{A_i}{B_i}\rceil$ (上取整) 次之后, 再升级该技能将不会改变攻击力。

现在小蓝可以总计升级 $M$ 次技能, 他可以任意选择升级的技能和次数。请你计算小蓝最多可以提高多少点攻击力?

【输入格式】

输入第一行包含两个整数 $N$ 和 $M$ 。

以下 $N$ 行每行包含两个整数 $A_i$ 和 $B_i$ 。

【输出格式】

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

【样例输入】

$\begin{array}{ll}3& 6\end{array}$

$\begin{array}{ll}10& 5\end{array}$

$\begin{array}{ll}9& 2\end{array}$

$\begin{array}{ll}8& 1\end{array}$

【样例输出】

$\begin{array}{ll}4& 7\end{array}$

【评测用例规模与约定】

对于 $40\%$ 的评测用例, $1\le N,M\le 1000$ ，

对于 $60\%$ 的评测用例, $1\le N\le 10^4,1\le M\le 10^7$ ；

对于所有评测用例, $1\le N\le 10^5,1\le M\le 2\times 10^9,1\le A_i,B_i\le 10^6$ 。

---

试题 I: 最优清零方案

时间限制: $3.0\mathrm{s}$ 内存限制: $512.0\mathrm{MB}$ 本题总分: 25 分

【问题描述】

给定一个长度为 $N$ 的数列 $A_1,A_2,\cdots ,A_N$ 。现在小蓝想通过若干次操作将这个数列中每个数字清零。

每次操作小蓝可以选择以下两种之一:

1. 选择一个大于 0 的整数, 将它减去 1 :
2. 选择连续 $K$ 个大于 0 的整数, 将它们各减去 1 。

小蓝最少经过几次操作可以将整个数列清零?

【输入格式】

输入第一行包含两个整数 $N$ 和 $K$ 。

第二行包含 $N$ 个整数 $A_1,A_2,\cdots ,A_N$ 。

【输出格式】

输出一个整数表示答案。

【样例输入】

$\begin{array}{ll}4& 2\end{array}$

$\begin{array}{llll}1& 2& 3& 4\end{array}$

【样例输出】

$\begin{array}{l}6\end{array}$

【评测用例规模与约定】

对于 $20\%$ 的评测用例， $1\le K\le N\le 10$ 。

对于 $40\%$ 的评测用例, $1\le K\le N\le 100$ 。

对于 $50\%$ 的评测用例, $1\le K\le N\le 1000$ 。

对于 $60\%$ 的评测用例, $1\le K\le N\le 10000$ 。

对于 $70\%$ 的评测用例, $1\le K\le N\le 100000$ 。

对于所有评测用例, $1\le K\le N\le 1000000,0\le A_i\le 1000000$ 。

---

试题 $\mathrm{J}:$ 推导部分和

时间限制: $1.0\mathrm{s}$ 内存限制: $512.0\mathrm{MB}$ 本题总分: 25 分

【问题描述】

对于一个长度为 $N$ 的整数数列 $A_1,A_2,\cdots A_N$, 小蓝想知道下标 $l$ 到 $r$ 的部分和 ${\sum }_{i=l}^r=A_l+A_{l+1}+\cdots +A_r$ 是多少?

然而, 小蓝并不知道数列中每个数的值是多少, 他只知道它的 $M$ 个部分和的值。其中第 $i$ 个部分和是下标 $l_i$ 到 $r_i$ 的部分和 ${\sum }_{j=l_i}^{r_i}=A_{l_i}+A_{l_i+1}+\cdots +A_{r_i}$,值是 $S_i$ 。

【输入格式】

第一行包含 3 个整数 $N、M$ 和 $Q$ 。分别代表数组长度、已知的部分和数量和询问的部分和数量。

接下来 $M$ 行, 每行包含 3 个整数 $l_i,r_i,S_i$ 。

接下来 $Q$ 行, 每行包含 2 个整数 $l$ 和 $r$, 代表一个小蓝想知道的部分和。

【输出格式】

对于每个询问, 输出一行包含一个整数表示答案。如果答案无法确定, 输出 UNKNOWN。

【样例输入】

$\begin{array}{lll}5& 3& 3\end{array}$

$\begin{array}{lll}1& 5& 15\end{array}$

$\begin{array}{lll}4& 5& 9\end{array}$

$\begin{array}{lll}2& 3& 5\end{array}$

$\begin{array}{ll}1& 5\end{array}$

$\begin{array}{ll}1& 3\end{array}$

$\begin{array}{ll}1& 2\end{array}$

【样例输出】

$\begin{array}{ll}1& 5\end{array}$

$\begin{array}{l}6\end{array}$

$\begin{array}{l}UNKNOWN\end{array}$

【评测用例规模与约定】

对于 $10\%$ 的评测用例, $1\le N,M,Q\le 10,-100\le S_i\le 100$ 。

对于 $20\%$ 的评测用例, $1\le N,M,Q\le 20,-1000\le S_i\le 1000$ 。

对于 $30\%$ 的评测用例, $1\le N,M,Q\le 50,-10000\le S_i\le 10000$ 。

对于 $40\%$ 的评测用例, $1\le N,M,Q\le 1000,-10^6\le S_i\le 10^6$ 。

对于 $60\%$ 的评测用例, $1\le N,M,Q\le 10000,-10^9\le S_i\le 10^9$ 。

对于所有评测用例, $1\le N,M,Q\le 10^5,-10^{12}\le S_i\le 10^{12},1\le l_i\le r_i\le N$,

$1\le l\le r\le N$ 。数据保证没有矛盾。