文章目录
- 发现宝藏
- 【考生须知】
- 试题 A: 火柴棒数字
- 试题 B: 小蓝与钥匙
- 试题 C: 内存空间
- 试题 D: 斐波那契数组
- 试题 E: 交通信号
- 试题 F: 数组个数
- 试题 G: 六六大顺
- 试题 H : \mathrm{H}: H: 选素数
- 试题 I: 图书借阅
- 试题
J
\mathrm{J}
J : 括号序列树
发现宝藏
前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。【宝藏入口】。
第十三届蓝桥杯大赛软件赛决赛（国赛） Java A 组【考生须知】
考试开始后, 选手首先下载题目, 并使用考场现场公布的解压密码解压试
考试时间为 4 小时。考试期间选手可汶览自己已经提交的答案, 被浏览的答案允许拷贝。时间截止后, 将无法继续提交或浏览答案。
对同一题目, 选手可多次提交答案, 以最后一次提交的答案为准。
选手必须通过浏览器方式提交自己的答案。选手在其它位置的作答或其它方式提交的答案无效。
试题包含 “结果填空” 和 “程序设计” 两种题型。
结果填空题: 要求选手根据题目描述直接填写结果。求解方式不限。不要求源代码。把结果填空的答案直接通过网页提交即可, 不要书写多余的内容。
程序设计题: 要求选手设计的程序对于给定的输入能给出正确的输出结果。考生的程序只有能运行出正确结果才有机会得分。
注意: 在评卷时使用的输入数据与试卷中给出的示例数据可能是不同的。选手的程序必须是通用的, 不能只对试卷中给定的数据有效。
所有源码必须在同一文件中。调试通过后，拷贝提交。
注意: 不要使用 package 语句。
注意: 选手代码的主类名必须为: Main, 否则会被判为无效代码。
注意: 如果程序中引用了类库, 在提交时必须将 import 语句与程序的其他部分同时提交。只允许使用 Java 自带的类库。
试题 A: 火柴棒数字
本题总分: 5 分
【问题描述】
小蓝最近迷上了用火柴棒拼数字字符, 方法如下图所示:
他只能拼 0 至 9 这十种数字字符, 其中每个数字字符需要的火柴棒的数目依次是: 6 , 2 , 5 , 5 , 4 , 5 , 6 , 3 , 7 , 6 6,2,5,5,4,5,6,3,7,6 6,2,5,5,4,5,6,3,7,6 。他不喜欢重复拼同一个数字字符, 所以对于每个数字字符他最多拼十个。小蓝会把拼出来的数字字符组合在一起形成一个整数,例如对于整数 345 , 需要的火柴棒的数目为 5 + 4 + 5 = 14 5+4+5=14 5+4+5=14 根。小蓝有 300 根火柴棒, 他想知道自己能拼出的最大整数是多少? 可以不使用完这 300 根火柴棒, 可以有多余的火柴棒剩下。
【答案提交】
这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。
试题 B: 小蓝与钥匙
本题总分: 5 分
【问题描述】
小蓝是幼儿园的老师, 他的班上有 28 个孩子, 今天他和孩子们一起进行了一个游戏。
小蓝所在的学校是寄宿制学校, 28 个孩子分别有一个自己的房间, 每个房间对应一把钥匙, 每把钥匙只能打开自己的门。现在小蓝让这 28 个孩子分别将自己宿舍的铜匙上交, 再把这 28 把钥匙随机打乱分给每个孩子一把钥匙, 有 28 ! = 28 × 27 × ⋯ × 1 28!=28 \times 27 \times \cdots \times 1 28!=28×27×⋯×1 种分配方案。小蓝想知道这些方案中, 有多少种方案恰有一半的孩子被分到自己房间的钥匙 (即有 14 个孩子分到的是自己房间的钥匙,有 14 个孩子分到的不是自己房间的钥匙)。
【答案提交】
这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。
试题 C: 内存空间
时间限制: 3.0s 内存限制: 512.0MB 本题总分: 10 分
【问题描述】
小蓝最近总喜欢计算自己的代码中定义的变量占用了多少内存空间。
为了简化问题, 变量的类型只有以下三种:
int: 整型变量, 一个 int 型变量占用 4 Byte 的内存空间。
long: 长整型变量, 一个 1 ong 型变量占用 8 Byte 的内存空间。
String: 字符串变量, 占用空间和字符串长度有关, 设字符串长度为 L L L,则字符串占用 L L L Byte 的内存空间, 如果字符串长度为 0 则占用 0 Byte 的内存空间。
定义变量的语句只有两种形式, 第一种形式为:
type var1=value1, var2=value 2 ⋯ 2 \cdots 2⋯;
定义了若干个 type 类型变量 var1、var 2 、 ⋯ 2 、 \cdots 2、⋯, 并且用 value1、value 2 ⋯ \cdots ⋯ 初始化,
多个变量之间用’,’ 分隔, 语句以’; '结尾, type 可能是 int、long 或 String。例如 int a = 1 , b = 5 , c = 6 a=1, b=5, c=6 a=1,b=5,c=6; 占用空间为 12 Byte; long a = 1 , b = 5 a=1, b=5 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 、 arr 2 ⋯ 1 、 \operatorname{arr} 2 \cdots 1、arr2⋯, 且数组的大小为 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 T T 条定义变量的语句, 请你帮他统计下一共占用了多少内存空间。结果的表示方式为: a G B b M B c K B d B a \mathrm{~GB} b \mathrm{MB} c \mathrm{~KB} d \mathrm{~B} a GBbMBc KBd B, 其中 a 、 b 、 c 、 d a 、 b 、 c 、 d a、b、c、d 为统计的结果, G B 、 M B 、 K B 、 B G B 、 M B 、 K B 、 B GB、MB、KB、B 为单位。优先用大的单位来表示, 1 G B = 1024 M B 1 \mathrm{~GB}=1024 \mathrm{MB} 1 GB=1024MB, 1 M B = 1024 K B , 1 K B = 1024 B 1 \mathrm{MB}=1024 \mathrm{~KB}, 1 \mathrm{~KB}=1024 \mathrm{~B} 1MB=1024 KB,1 KB=1024 B ，其中 B \mathrm{B} B 表示 Byte。如果 a 、 b 、 c 、 d a 、 b 、 c 、 d a、b、c、d 中的某几个数字为 0 , 那么不必输出这几个数字及其单位。题目保证一行中只有一句定义变量的语句, 且每条语句都满足题干中描述的定义格式, 所有的变量名都是合法的且均不重复。题目中的数据很规整, 和上述给出的例子类似, 除了类型后面有一个空格, 以及定义数组时 new 后面的一个空格之外, 不会出现多余的空格。
【输入格式】
输入的第一行包含一个整数 T T T, 表示有 T T T 句变量定义的语句。接下来 T T T 行, 每行包含一句变量定义语句。
【输出格式】
输出一行包含一个字符串, 表示所有语句所占用空间的总大小。
【样例输入 1 】
1 \begin{array}{llll}1 \end{array} 1
l o n g [ ] n u m s = n e w l o n g [ 131072 ] ; \begin{array}{llll}long[] nums=new long[131072];\end{array} long[]nums=newlong[131072];
【样例输出 1 】 \mathbf{1 】} 1】
1 M B 1 \mathrm{MB} 1MB
【样例输入 2】
4 \begin{array}{llll}4\end{array} 4
i n t a = 0 , b = 0 ; \begin{array}{llll}int a=0,b=0;\end{array} inta=0,b=0;
l o n g x = 0 , y = 0 ; \begin{array}{llll}long x=0,y=0;\end{array} longx=0,y=0;
S t r i n g s 1 = " h e l l o " , s 2 = " w o r l d " ; \begin{array}{llll}String s1="hello",s2="world";\end{array} Strings1="hello",s2="world";
l o n g [ ] a r r 1 = n e w l o n g [ 100000 ] , a r r 2 = n e w l o n g [ 100000 ] ; \begin{array}{llll}long[] arr1=new long[100000], arr2=new long[100000];\end{array} long[]arr1=newlong[100000],arr2=newlong[100000];
【样例输出 2】
1MB538KB546B
【样例说明】
样例 1, 占用的空间为 131072 × 8 = 1048576 B 131072 \times 8=1048576 \mathrm{~B} 131072×8=1048576 B, 换算过后正好是 1 M B 1 \mathrm{MB} 1MB, 其它三个单位 G B 、 K B 、 B \mathrm{GB} 、 \mathrm{KB、B} GB、KB、B 前面的数字都为 0 , 所以不用输出。
样例 2 , 占用的空间为 4 × 2 + 8 × 2 + 10 + 8 × 100000 × 2 B 4 \times 2+8 \times 2+10+8 \times 100000 \times 2 B 4×2+8×2+10+8×100000×2B, 换算后是 1MB538KB546B。
【评测用例规模与约定】
对于所有评测用例, 1 ≤ T ≤ 10 1 \leq T \leq 10 1≤T≤10, 每条变量定义语句的长度不会超过 1000 。所有的变量名称长度不会超过 10 , 且都由小写字母和数字组成。对于整型变量, 初始化的值均是在其表示范围内的十进制整数, 初始化的值不会是变量。对于 String 类型的变量, 初始化的内容长度不会超过 50 , 且内容仅包含小写字母和数字, 初始化的值不会是变量。对于数组类型变量, 数组的长度为一个整数, 范围为: [ 0 , 2 30 ] \left[0,2^{30}\right] [0,230], 数组的长度不会是变量。 T T T 条语句定义的变量所占的内存空间总大小不会超过 1 G B 1 \mathrm{~GB} 1 GB, 且大于 0 B 0 \mathrm{~B} 0 B 。
试题 D: 斐波那契数组
时间限制: 3.0 s 3.0 \mathrm{~s} 3.0 s 内存限制: 512.0 M B 512.0 \mathrm{MB} 512.0MB 本题总分: 10 分
【问题描述】
如果数组 A = ( a 0 , a 1 , ⋯ , a n − 1 ) A=\left(a_{0}, a_{1}, \cdots, a_{n-1}\right) A=(a0,a1,⋯,an−1) 满足以下条件, 就说它是一个斐波那契数组:
- n ≥ 2 n \geq 2 n≥2;
- a 0 = a 1 ; a_{0}=a_{1} ; a0=a1;
- 对于所有的 i ( i ≥ 2 ) i(i \geq 2) i(i≥2), 都满足 a i = a i − 1 + a i − 2 a_{i}=a_{i-1}+a_{i-2} ai=ai−1+ai−2 。
现在, 给出一个数组 A \boldsymbol{A} A, 你可以执行任意次修改, 每次修改将数组中的某个位置的元素修改为一个大于 0 的整数。请问最少修改几个元素之后, 数组 A A A会变成一个斐波那契数组。
【输入格式】
输入的第一行包含一个整数 n n n, 表示数组 A A A 中的元素个数。
第二行包含 n n n 个整数 a 0 , a 1 , ⋯ , a n − 1 a_{0}, a_{1}, \cdots, a_{n-1} a0,a1,⋯,an−1, 相邻两个整数之间用一个空格分隔。
【输出格式】
输出一行包含一个整数表示最少需要修改数组 A A A 中的几个元素之后, 数组 A A A 可以变为一个斐波那契数组。
【样例输入】
5 \begin{array}{llll}5\end{array} 5
1 2 2 4 8 \begin{array}{llll}1&2&2&4&8\end{array} 12248
【样例输出】
3 \begin{array}{llll}3\end{array} 3
【样例说明】
将原数组修改为 ( 1 , 1 , 2 , 3 , 5 ) (1,1,2,3,5) (1,1,2,3,5), 最少修改三个元素变成了一个斐波那契数组。
【评测用例规模与约定】
对于所有评测用例, 2 ≤ n ≤ 1 0 5 , 1 ≤ a i ≤ 1 0 6 2 \leq n \leq 10^{5}, 1 \leq a_{i} \leq 10^{6} 2≤n≤105,1≤ai≤106 。
试题 E: 交通信号
时间限制: 3.0s 内存限制: 512.0MB 本题总分: 15 分
【问题描述】
LQ 市的交通系统可以看成由 n n n 个结点和 m m m 条有向边组成的有向图。在每条边上有一个信号灯, 会不断按绿黄红黄绿黄红黄… 的顺序循环 (初始时刚好变到绿灯)。当信号奵为绿灯时允许正向通行, 红奵时允许反向通行, 黄奵时不允许通行。每条边上的信号奵的三种颜色的持续时长都互相独立, 其中黄奵的持续时长等同于走完路径的耗时。当走到一条边上时, 需要观察边上的信号奵,如果允许通行则可以通过此边, 在通行过程中不再受信号奵的影响: 否则需要等待, 直到允许通行。
请问从结点 s s s 到结点 t t t 所需的最短时间是多少, 如果 s s s 无法到达 t t t 则输出 -1 .
【输入格式】
输入的第一行包含四个整数 n , m , s , t n, m, s, t n,m,s,t, 相邻两个整数之间用一个空格分隔。
接下来 m m m 行, 每行包含五个整数 u i , v i , g i , r i , d i u_{i}, v_{i}, g_{i}, r_{i}, d_{i} ui,vi,gi,ri,di, 相邻两个整数之间用一个空格分隔, 分别表示一条边的起点, 终点, 绿奵、红奵的持续时长和距离 (黄奵的持续时长).
【输出格式】
输出一行包含一个整数表示从结点 s s s 到达 t t t 所需的最短时间。
【样例输入】
4 4 1 4 \begin{array}{llll}4 & 4 & 1 & 4\end{array} 4414
1 2 1 2 6 \begin{array}{llllllll}1 & 2 & 1 & 2 & 6\end{array} 12126
4 2 1 1 5 \begin{array}{lllllllll}4 & 2 & 1 & 1 & 5\end{array} 42115
1 3 1 1 1 \begin{array}{lllllll}1 & 3 & 1 & 1 & 1\end{array} 13111
3 4 1 99 1 \begin{array}{llllll}3 & 4 & 1 & 99 & 1\end{array} 341991
【样例输出】
11 \begin{array}{llll}11\end{array} 11
【评测用例规模与约定】
对于 40 % 40 \% 40% 的评测用例, n ≤ 500 , 1 ≤ g i , r i , d i ≤ 100 n \leq 500,1 \leq g_{i}, r_{i}, d_{i} \leq 100 n≤500,1≤gi,ri,di≤100;
对于 70 % 70 \% 70% 的评测用例, n ≤ 5000 n \leq 5000 n≤5000 ；
对于所有评测用例, 1 ≤ n ≤ 100000 , 1 ≤ m ≤ 200000 , 1 ≤ s , t ≤ n 1 \leq n \leq 100000,1 \leq m \leq 200000,1 \leq s, t \leq n 1≤n≤100000,1≤m≤200000,1≤s,t≤n, 1 ≤ u i , v i ≤ n , 1 ≤ g i , r i , d i ≤ 1 0 9 。 1 \leq u_{i}, v_{i} \leq n, 1 \leq g_{i}, r_{i}, d_{i} \leq 10^{9} 。 1≤ui,vi≤n,1≤gi,ri,di≤109。
试题 F: 数组个数
时间限制: 3.0 s 3.0 \mathrm{~s} 3.0 s 内存限制: 512.0 M B 512.0 \mathrm{MB} 512.0MB 本题总分: 15 分
【问题描述】
小蓝有一个长度为 n n n 的数组 B = ( b 0 , b 1 , ⋯ , b n − 1 ) B=\left(b_{0}, b_{1}, \cdots, b_{n-1}\right) B=(b0,b1,⋯,bn−1), 数组 B B B 是由另一个长度为 n n n 的环形数组 A = ( a 0 , a 1 , ⋯ , a n − 1 ) A=\left(a_{0}, a_{1}, \cdots, a_{n-1}\right) A=(a0,a1,⋯,an−1) 经过一次相邻最大化操作得到的, 其中 a i a_{i} ai与 a i + 1 a_{i+1} ai+1 相邻, a 0 a_{0} a0 与 a n − 1 a_{n-1} an−1 相邻。
形式化描述为:
b i = { max ( a n − 1 , a 0 , a 1 ) , ( i = 0 ) max ( a i − 1 , a i , a i + 1 ) , ( 0
