第十三届蓝桥杯决赛（国赛）真题 Java A 组【原卷】

发现宝藏

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

---

第十三届蓝桥杯大赛软件赛决赛（国赛） Java A 组

【考生须知】

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

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

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

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

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

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

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

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

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

注意: 不要使用 package 语句。

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

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

---

试题 A: 火柴棒数字

本题总分: 5 分

【问题描述】

小蓝最近迷上了用火柴棒拼数字字符, 方法如下图所示:

他只能拼 0 至 9 这十种数字字符, 其中每个数字字符需要的火柴棒的数目依次是: $6,2,5,5,4,5,6,3,7,6$ 。他不喜欢重复拼同一个数字字符, 所以对于每个数字字符他最多拼十个。小蓝会把拼出来的数字字符组合在一起形成一个整数,例如对于整数 345 , 需要的火柴棒的数目为 $5+4+5=14$ 根。小蓝有 300 根火柴棒, 他想知道自己能拼出的最大整数是多少? 可以不使用完这 300 根火柴棒, 可以有多余的火柴棒剩下。

【答案提交】

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

---

试题 B: 小蓝与钥匙

本题总分: 5 分

【问题描述】

小蓝是幼儿园的老师, 他的班上有 28 个孩子, 今天他和孩子们一起进行了一个游戏。

小蓝所在的学校是寄宿制学校, 28 个孩子分别有一个自己的房间, 每个房间对应一把钥匙, 每把钥匙只能打开自己的门。现在小蓝让这 28 个孩子分别将自己宿舍的铜匙上交, 再把这 28 把钥匙随机打乱分给每个孩子一把钥匙, 有 $28!=28\times 27\times \cdots \times 1$ 种分配方案。小蓝想知道这些方案中, 有多少种方案恰有一半的孩子被分到自己房间的钥匙 (即有 14 个孩子分到的是自己房间的钥匙,有 14 个孩子分到的不是自己房间的钥匙)。

【答案提交】

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

---

试题 C: 内存空间

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

【问题描述】

小蓝最近总喜欢计算自己的代码中定义的变量占用了多少内存空间。

为了简化问题, 变量的类型只有以下三种:

int: 整型变量, 一个 int 型变量占用 4 Byte 的内存空间。

long: 长整型变量, 一个 1 ong 型变量占用 8 Byte 的内存空间。

String: 字符串变量, 占用空间和字符串长度有关, 设字符串长度为 $L$,则字符串占用 $L$ Byte 的内存空间, 如果字符串长度为 0 则占用 0 Byte 的内存空间。

定义变量的语句只有两种形式, 第一种形式为:

type var1=value1, var2=value $2\cdots$;

定义了若干个 type 类型变量 var1、var $2、\cdots$, 并且用 value1、value 2 $\cdots$ 初始化,

多个变量之间用’,’ 分隔, 语句以’; '结尾, type 可能是 int、long 或 String。例如 int $a=1,b=5,c=6$; 占用空间为 12 Byte; long $a=1,b=5$;占用空间为 16 Byte; String s 1=“”, s 2=“hello”, s 3=“world”; 占用空间为 10 Byte

第二种形式为:

type[] arr1=new type[size1], arr2=new type[size2]. ;

定义了若干 type 类型的一维数组变量 arr $1、\mathrm{arr}2\cdots$, 且数组的大小为 size1、size2 $\cdots$, 多个变量之间用’, ’ 进行分隔, 语句以’; '结尾, type 只可能是 int 或 long。例如 int[] a1=new int[10]; 占用的内存空间为 40

Byte; long[] a1=new long[10],a2=new long[10]; 占用的内存空间为 160 Byte.

已知小蓝有 $T$ 条定义变量的语句, 请你帮他统计下一共占用了多少内存空间。结果的表示方式为: $a\mathrm{GB}b\mathrm{MB}c\mathrm{KB}d\mathrm{B}$, 其中 $a、b、c、d$ 为统计的结果, $GB、MB、KB、B$ 为单位。优先用大的单位来表示, $1\mathrm{GB}=1024\mathrm{MB}$, $1\mathrm{MB}=1024\mathrm{KB},1\mathrm{KB}=1024\mathrm{B}$ ，其中 $\mathrm{B}$ 表示 Byte。如果 $a、b、c、d$ 中的某几个数字为 0 , 那么不必输出这几个数字及其单位。题目保证一行中只有一句定义变量的语句, 且每条语句都满足题干中描述的定义格式, 所有的变量名都是合法的且均不重复。题目中的数据很规整, 和上述给出的例子类似, 除了类型后面有一个空格, 以及定义数组时 new 后面的一个空格之外, 不会出现多余的空格。

【输入格式】

输入的第一行包含一个整数 $T$, 表示有 $T$ 句变量定义的语句。接下来 $T$ 行, 每行包含一句变量定义语句。

【输出格式】

输出一行包含一个字符串, 表示所有语句所占用空间的总大小。

【样例输入 1 】

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

$\begin{array}{l}long[]nums=newlong[131072];\end{array}$

【样例输出 $1】$

$1\mathrm{MB}$

【样例输入 2】

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

$\begin{array}{l}inta=0,b=0;\end{array}$

$\begin{array}{l}longx=0,y=0;\end{array}$

$\begin{array}{l}Strings1="hello",s2="world";\end{array}$

$\begin{array}{l}long[]arr1=newlong[100000],arr2=newlong[100000];\end{array}$

【样例输出 2】

1MB538KB546B

【样例说明】

样例 1, 占用的空间为 $131072\times 8=1048576\mathrm{B}$, 换算过后正好是 $1\mathrm{MB}$, 其它三个单位 $\mathrm{GB}、\mathrm{KB}、\mathrm{B}$ 前面的数字都为 0 , 所以不用输出。

样例 2 , 占用的空间为 $4\times 2+8\times 2+10+8\times 100000\times 2B$, 换算后是 1MB538KB546B。

【评测用例规模与约定】

对于所有评测用例, $1\le T\le 10$, 每条变量定义语句的长度不会超过 1000 。所有的变量名称长度不会超过 10 , 且都由小写字母和数字组成。对于整型变量, 初始化的值均是在其表示范围内的十进制整数, 初始化的值不会是变量。对于 String 类型的变量, 初始化的内容长度不会超过 50 , 且内容仅包含小写字母和数字, 初始化的值不会是变量。对于数组类型变量, 数组的长度为一个整数, 范围为: $\left[0,2^{30}\right]$, 数组的长度不会是变量。 $T$ 条语句定义的变量所占的内存空间总大小不会超过 $1\mathrm{GB}$, 且大于 $0\mathrm{B}$ 。

---

试题 D: 斐波那契数组

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

【问题描述】

如果数组 $A=\left(a_0,a_1,\cdots ,a_{n-1}\right)$ 满足以下条件, 就说它是一个斐波那契数组:

1. $n\ge 2$;
2. $a_0=a_1;$
3. 对于所有的 $i(i\ge 2)$, 都满足 $a_i=a_{i-1}+a_{i-2}$ 。

现在, 给出一个数组 $\mathbf{A}$, 你可以执行任意次修改, 每次修改将数组中的某个位置的元素修改为一个大于 0 的整数。请问最少修改几个元素之后, 数组 $A$会变成一个斐波那契数组。

【输入格式】

输入的第一行包含一个整数 $n$, 表示数组 $A$ 中的元素个数。

第二行包含 $n$ 个整数 $a_0,a_1,\cdots ,a_{n-1}$, 相邻两个整数之间用一个空格分隔。

【输出格式】

输出一行包含一个整数表示最少需要修改数组 $A$ 中的几个元素之后, 数组 $A$ 可以变为一个斐波那契数组。

【样例输入】

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

$\begin{array}{llllc}1& 2& 2& 4& 8\end{array}$

【样例输出】

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

【样例说明】

将原数组修改为 $(1,1,2,3,5)$, 最少修改三个元素变成了一个斐波那契数组。

【评测用例规模与约定】

对于所有评测用例, $2\le n\le 10^5,1\le a_i\le 10^6$ 。

---

试题 E: 交通信号

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

【问题描述】

LQ 市的交通系统可以看成由 $n$ 个结点和 $m$ 条有向边组成的有向图。在每条边上有一个信号灯, 会不断按绿黄红黄绿黄红黄… 的顺序循环 (初始时刚好变到绿灯)。当信号奵为绿灯时允许正向通行, 红奵时允许反向通行, 黄奵时不允许通行。每条边上的信号奵的三种颜色的持续时长都互相独立, 其中黄奵的持续时长等同于走完路径的耗时。当走到一条边上时, 需要观察边上的信号奵,如果允许通行则可以通过此边, 在通行过程中不再受信号奵的影响: 否则需要等待, 直到允许通行。

请问从结点 $s$ 到结点 $t$ 所需的最短时间是多少, 如果 $s$ 无法到达 $t$ 则输出 -1 .

【输入格式】

输入的第一行包含四个整数 $n,m,s,t$, 相邻两个整数之间用一个空格分隔。

接下来 $m$ 行, 每行包含五个整数 $u_i,v_i,g_i,r_i,d_i$, 相邻两个整数之间用一个空格分隔, 分别表示一条边的起点, 终点, 绿奵、红奵的持续时长和距离 (黄奵的持续时长).

【输出格式】

输出一行包含一个整数表示从结点 $s$ 到达 $t$ 所需的最短时间。

【样例输入】

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

$\begin{array}{lllll}1& 2& 1& 2& 6\end{array}$

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

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

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

【样例输出】

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

【评测用例规模与约定】

对于 $40\%$ 的评测用例, $n\le 500,1\le g_i,r_i,d_i\le 100$;

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

对于所有评测用例, $1\le n\le 100000,1\le m\le 200000,1\le s,t\le n$,$1\le u_i,v_i\le n,1\le g_i,r_i,d_i\le 10^9。$

---

试题 F: 数组个数

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

【问题描述】

小蓝有一个长度为 $n$ 的数组 $B=\left(b_0,b_1,\cdots ,b_{n-1}\right)$, 数组 $B$ 是由另一个长度为 $n$ 的环形数组 $A=\left(a_0,a_1,\cdots ,a_{n-1}\right)$ 经过一次相邻最大化操作得到的, 其中 $a_i$与 $a_{i+1}$ 相邻, $a_0$ 与 $a_{n-1}$ 相邻。

形式化描述为:

$$b_i=\{\begin{array}{ll}\max \left(a_{n-1},a_0,a_1\right),& (i=0)\\ \max \left(a_{i-1},a_i,a_{i+1}\right),& (0<i<n-1)\\ \max \left(a_{n-2},a_{n-1},a_0\right),& (i=n-1)\end{array}$$

小蓝想知道, 可能有多少个满足条件的数组 $A$, 经过一次相邻最大化操作后能得到数组 $B$, 注意 $A$ 中的每个元素都要求为非负整数。

【输入格式】

输入的第一行包含一个整数 $n$, 表示数组长度。

第二行包含 $n$ 个整数 $b_0,b_1,\cdots ,b_{n-1}$, 相邻两个整数之间用一个空格分隔。

【输出格式】

输出一行包含一个整数表示答案, 答案可能很大, 请输出答案除以 1000000007 后的余数。

【样例输入】

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

$\begin{array}{lllll}8& 6& 1& 8& 8\end{array}$

【样例输出】

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

【样例说明】

可能的 $A$ 数组有 7 个: $(6,0,0,1,8)、(6,0,1,0,8)、(6,0,1,1,8)、(6,1,0,0,8)$ 、 $(6,1,0,1,8)、(6,1,1,0,8)、(6,1,1,1,8)$ 。

【评测用例规模与约定】

对于 $30\%$ 的评测用例, $3\le n\le 10$;

对于 $60\%$ 的评测用例， $3\le n\le 100$;

对于所有评测用例, $3\le n\le 1000,0\le b_i\le 10$ 。

---

试题 G: 六六大顺

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

【问题描述】

六六大顺, 本指农历六月初六。多用于祝福中年人士家庭幸福, 工作顺利,事业有成, 身体健康。源自《左传》“君义, 臣行, 父慈, 子孝, 兄爱, 弟敬,此数者䍗谓六顺也。”

6 在我国自古以来是一个吉祥的数字, 定义数列 $A=\left(a_1,a_2,\cdots ,a_i,\cdots \right)$,其中 $a_1=6,a_2=66,\cdots ,a_i=10\cdot a_{i-1}+6$ 。

定义一个数列 $B=\left(b_1,b_2,\cdots ,b_i,\cdots \right)$, 其中 $b_1=6\times 6,b_2=66\times 66,\cdots$, $b_i=a_i\cdot a_i$ 。

现在小蓝想知道数列 $B$ 的前 $n$ 项的和是多少, 你能帮帮小蓝吗?

【输入格式】

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

【输出格式】

输出一行包含一个整数表示数列 $B$ 前 $n$ 项的和。

【样例输入】

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

【样例输出】

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

【样例说明】

$b_1=6\times 6=36,b_2=66\times 66=4356,b_3=666\times 666=443556$, 所以前三项的和为 $36+4356+443556=447948$ 。

【评测用例规模与约定】

对于 $20\%$ 的评测用例, $1\le n\le 100$;

对于 $50\%$ 的评测用例, $1\le n\le 100000$;

对于所有评测用例, $1\le n\le 10000000$ 。

---

试题 $\mathrm{H}:$ 选素数

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

【问题描述】

小蓝有一个数 $x$, 每次操作小蓝会选择一个小于 $x$ 的素数 $p$, 然后在 $x$ 成为 $p$ 的倍数前不断将 $x$ 加 1 , (如果 $x$ 一开始就是 $p$ 的倍数则 $x$ 不变)。

小乔看到了小蓝进行了 2 次上述操作后得到的结果 $n$, 他想知道 $x$ 在一开始是多少。如果有多种可能, 他想知道 $x$ 一开始最小可以是多少, 而如果不存在任何解, 说明小乔看错了, 此时请输出 -1 。

【输入格式】

输入一行包含一个整数 $n$, 表示经过两次操作后 $x$ 的值。

【输出格式】

输出一行包含一个整数表示 $x$ 的初始值。如果有多个解, 输出最小的。如果不存在解, 请输出 -1 。

【样例输入】

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

【样例输出】

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

【评测用例规模与约定】

对于 $60\%$ 的评测用例, $1\le n\le 5000$;

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

---

试题 I: 图书借阅

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

【问题描述】

小蓝是一所图书馆的管理员, 图书馆中目前有 $n$ 种书, 第 $i$ 种书有 $a_i$ 本。

小蓝目前有 $m$ 条未来若干天中用户的预约借阅记录, 每个借阅记录由 $b_i,l_i,r_i$ 组成, 表示在 $l_i$ 日要借用一本书 $b_i,r_i$ 日归还, $r_i$ 日结束后图书馆才可以将这本书重新借出。

小蓝分析了一下预约借阅记录, 发现现有的书不一定能满足所有人的预约请求, 于是小蓝打算额外购买一些书加入到图书馆。小蓝的预算有限, 请问如果额外添加不超过 $x$ 本书, 最多有多少条预约记录能得到满足? 小蓝可以选取一部分记录使其满足, 不一定需要按借阅或预定的时间顺序满足。

【输入格式】

输入的第一行包含三个整数 $n,m,x$, 相邻两个整数之间用一个空格分隔。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots ,a_n$, 相邻两个整数之间用一个空格分隔, 表示目前拥有的每种书的本数。

接下来 $m$ 行, 每行包含 3 个整数 $b_i,l_i,r_i$, 相邻两个整数之间用一个空格分隔, 表示一条预约借阅记录。

【输出格式】

输出一行包含一个整数表示给定条件下最多能满足预约借阅的记录数。

【样例输入】

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

$\begin{array}{lll}1& 0& 2\end{array}$

$\begin{array}{lll}1& 2& 4\end{array}$

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

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

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

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

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

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

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

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

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

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

【样例输出】

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

【评测用例规模与约定】

对于 $10\%$ 的评测用例, $n,m\le 10,l_i\le r_i\le 10$;

对于 $50\%$ 的评测用例, $n,m\le 2000,l_i\le r_i\le 5000$ :

对于所有评测用例, $1\le n\le 100000,1\le x\le m\le 200000,1\le b_i\le n$, $1\le l_i\le r_i\le 10^6,0\le a_i\le 10^5$ 。

---

试题 $\mathrm{J}$ : 括号序列树

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

【问题描述】

有一棵二叉树, 根结点上有一个空字符串, 每个点的左儿子上的字符串为其父亲结点的字符串尾部额外加一个左括号, 右儿子则是在尾部加一个右括号。树中的每个叶子结点上的字符串都分别和每个由 $n$ 对括号组成的合法括号序列一一对应。

给定 $n$, 求此时这棵树的最大匹配所含的边数。

【输入格式】

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

【输出格式】

输出一行包含一个整数表示满足条件的序列的数量, 答案可能很大, 请输出答案除以 998244353 的余数。

【样例输入】

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

【样例输出】

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

【评测用例规模与约定】

对于 $20\%$ 的评测用例， $n\le 10$ ，

对于 $40\%$ 的评测用例, $n\le 300$

对于 $60\%$ 的评测用例， $n\le 5000$;

对于 $85\%$ 的评测用例, $n\le 10^5$;

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