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

文章目录

发现宝藏

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


第十三届蓝桥杯大赛软件赛决赛(国赛)
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 1arr2, 且数组的大小为 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 abcd 为统计的结果, G B 、 M B 、 K B 、 B G B 、 M B 、 K B 、 B GBMBKBB 为单位。优先用大的单位来表示, 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 abcd 中的某几个数字为 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} GBKBB 前面的数字都为 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 1T10, 每条变量定义语句的长度不会超过 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,,an1) 满足以下条件, 就说它是一个斐波那契数组:

  1. n ≥ 2 n \geq 2 n2;
  2. a 0 = a 1 ; a_{0}=a_{1} ; a0=a1;
  3. 对于所有的 i ( i ≥ 2 ) i(i \geq 2) i(i2), 都满足 a i = a i − 1 + a i − 2 a_{i}=a_{i-1}+a_{i-2} ai=ai1+ai2

现在, 给出一个数组 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,,an1, 相邻两个整数之间用一个空格分隔。

【输出格式】

输出一行包含一个整数表示最少需要修改数组 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} 2n105,1ai106


试题 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 n500,1gi,ri,di100;

对于 70 % 70 \% 70% 的评测用例, n ≤ 5000 n \leq 5000 n5000

对于所有评测用例, 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 1n100000,1m200000,1s,tn, 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} 。 1ui,vin,1gi,ri,di109


试题 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,,bn1), 数组 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,,an1) 经过一次相邻最大化操作得到的, 其中 a i a_{i} ai a i + 1 a_{i+1} ai+1 相邻, a 0 a_{0} a0 a n − 1 a_{n-1} an1 相邻。

形式化描述为:

b i = { max ⁡ ( a n − 1 , a 0 , a 1 ) , ( i = 0 ) max ⁡ ( a i − 1 , a i , a i + 1 ) , ( 0 < i < n − 1 ) max ⁡ ( a n − 2 , a n − 1 , a 0 ) , ( i = n − 1 ) b_{i}= \begin{cases}\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{cases} bi= max(an1,a0,a1),max(ai1,ai,ai+1),max(an2,an1,a0),(i=0)(0<i<n1)(i=n1)

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

【输入格式】

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

第二行包含 n n n 个整数 b 0 , b 1 , ⋯ , b n − 1 b_{0}, b_{1}, \cdots, b_{n-1} b0,b1,,bn1, 相邻两个整数之间用一个空格分隔。

【输出格式】

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

【样例输入】

5 \begin{array}{llll}5\end{array} 5

8 6 1 8 8 \begin{array}{llllll}8 & 6 & 1 & 8 & 8\end{array} 86188

【样例输出】

7 \begin{array}{llll}7\end{array} 7

【样例说明】

可能的 A A A 数组有 7 个: ( 6 , 0 , 0 , 1 , 8 ) 、 ( 6 , 0 , 1 , 0 , 8 ) 、 ( 6 , 0 , 1 , 1 , 8 ) 、 ( 6 , 1 , 0 , 0 , 8 ) (6,0,0,1,8) 、(6,0,1,0,8) 、(6,0,1,1,8) 、(6,1,0,0,8) (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 ) (6,1,0,1,8) 、(6,1,1,0,8) 、(6,1,1,1,8) (6,1,0,1,8)(6,1,1,0,8)(6,1,1,1,8)

【评测用例规模与约定】

对于 30 % 30 \% 30% 的评测用例, 3 ≤ n ≤ 10 3 \leq n \leq 10 3n10;

对于 60 % 60 \% 60% 的评测用例, 3 ≤ n ≤ 100 3 \leq n \leq 100 3n100;

对于所有评测用例, 3 ≤ n ≤ 1000 , 0 ≤ b i ≤ 10 3 \leq n \leq 1000,0 \leq b_{i} \leq 10 3n1000,0bi10


试题 G: 六六大顺

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

【问题描述】

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

6 在我国自古以来是一个吉祥的数字, 定义数列 A = ( a 1 , a 2 , ⋯ , a i , ⋯ ) A=\left(a_{1}, a_{2}, \cdots, a_{i}, \cdots\right) A=(a1,a2,,ai,),其中 a 1 = 6 , a 2 = 66 , ⋯ , a i = 10 ⋅ a i − 1 + 6 a_{1}=6, a_{2}=66, \cdots, a_{i}=10 \cdot a_{i-1}+6 a1=6,a2=66,,ai=10ai1+6

定义一个数列 B = ( b 1 , b 2 , ⋯ , b i , ⋯ ) B=\left(b_{1}, b_{2}, \cdots, b_{i}, \cdots\right) B=(b1,b2,,bi,), 其中 b 1 = 6 × 6 , b 2 = 66 × 66 , ⋯ b_{1}=6 \times 6, b_{2}=66 \times 66, \cdots b1=6×6,b2=66×66,, b i = a i ⋅ a i b_{i}=a_{i} \cdot a_{i} bi=aiai

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

【输入格式】

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

【输出格式】

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

【样例输入】

3 \begin{array}{llll}3\end{array} 3

【样例输出】

447948 \begin{array}{llll}447948\end{array} 447948

【样例说明】

b 1 = 6 × 6 = 36 , b 2 = 66 × 66 = 4356 , b 3 = 666 × 666 = 443556 b_{1}=6 \times 6=36, b_{2}=66 \times 66=4356, b_{3}=666 \times 666=443556 b1=6×6=36,b2=66×66=4356,b3=666×666=443556, 所以前三项的和为 36 + 4356 + 443556 = 447948 36+4356+443556=447948 36+4356+443556=447948

【评测用例规模与约定】

对于 20 % 20 \% 20% 的评测用例, 1 ≤ n ≤ 100 1 \leq n \leq 100 1n100;

对于 50 % 50 \% 50% 的评测用例, 1 ≤ n ≤ 100000 1 \leq n \leq 100000 1n100000;

对于所有评测用例, 1 ≤ n ≤ 10000000 1 \leq n \leq 10000000 1n10000000


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

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

【问题描述】

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

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

【输入格式】

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

【输出格式】

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

【样例输入】

22 \begin{array}{llll}22\end{array} 22

【样例输出】

8 \begin{array}{llll}8\end{array} 8

【评测用例规模与约定】

对于 60 % 60 \% 60% 的评测用例, 1 ≤ n ≤ 5000 1 \leq n \leq 5000 1n5000;

对于所有评测用例, 1 ≤ n ≤ 1 0 6 1 \leq n \leq 10^{6} 1n106


试题 I: 图书借阅

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

【问题描述】

小蓝是一所图书馆的管理员, 图书馆中目前有 n n n 种书, 第 i i i 种书有 a i a_{i} ai 本。

小蓝目前有 m m m 条未来若干天中用户的预约借阅记录, 每个借阅记录由 b i , l i , r i b_{i}, l_{i}, r_{i} bi,li,ri 组成, 表示在 l i l_{i} li 日要借用一本书 b i , r i b_{i}, r_{i} bi,ri 日归还, r i r_{i} ri 日结束后图书馆才可以将这本书重新借出。

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

【输入格式】

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

第二行包含 n n n 个整数 a 1 , a 2 , ⋯ , a n a_{1}, a_{2}, \cdots, a_{n} a1,a2,,an, 相邻两个整数之间用一个空格分隔, 表示目前拥有的每种书的本数。

接下来 m m m 行, 每行包含 3 个整数 b i , l i , r i b_{i}, l_{i}, r_{i} bi,li,ri, 相邻两个整数之间用一个空格分隔, 表示一条预约借阅记录。

【输出格式】

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

【样例输入】

3 11 3 \begin{array}{llll}3 & 11 & 3\end{array} 3113

1 0 2 \begin{array}{llll}1 & 0 & 2\end{array} 102

1 2 4 \begin{array}{llll}1 & 2 & 4\end{array} 124

1 1 2 \begin{array}{llll}1 & 1 & 2\end{array} 112

1 4 5 \begin{array}{llll}1 & 4 &5\end{array} 145

1 3 5 \begin{array}{llll}1 & 3 & 5\end{array} 135

1 1 3 \begin{array}{llll}1 & 1& 3\end{array} 113

2 1 1 \begin{array}{llll}2 & 1 & 1\end{array} 211

2 2 2 \begin{array}{llll}2& 2 & 2\end{array} 222

2 3 3 \begin{array}{llll}2 & 3& 3\end{array} 233

2 1 2 \begin{array}{llll}2& 1 & 2\end{array} 212

2 3 4 \begin{array}{llll}2& 3 & 4\end{array} 234

3 1 5 \begin{array}{llll}3 & 1 &5\end{array} 315

【样例输出】

10 \begin{array}{llll}10\end{array} 10

【评测用例规模与约定】

对于 10 % 10 \% 10% 的评测用例, n , m ≤ 10 , l i ≤ r i ≤ 10 n, m \leq 10, l_{i} \leq r_{i} \leq 10 n,m10,liri10;

对于 50 % 50 \% 50% 的评测用例, n , m ≤ 2000 , l i ≤ r i ≤ 5000 n, m \leq 2000, l_{i} \leq r_{i} \leq 5000 n,m2000,liri5000 :

对于所有评测用例, 1 ≤ n ≤ 100000 , 1 ≤ x ≤ m ≤ 200000 , 1 ≤ b i ≤ n 1 \leq n \leq 100000,1 \leq x \leq m \leq 200000,1 \leq b_{i} \leq n 1n100000,1xm200000,1bin, 1 ≤ l i ≤ r i ≤ 1 0 6 , 0 ≤ a i ≤ 1 0 5 1 \leq l_{i} \leq r_{i} \leq 10^{6}, 0 \leq a_{i} \leq 10^{5} 1liri106,0ai105


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

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

【问题描述】

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

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

【输入格式】

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

【输出格式】

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

【样例输入】

9 \begin{array}{llll}9\end{array} 9

【样例输出】

10350 \begin{array}{llll}10350\end{array} 10350

【评测用例规模与约定】

对于 20 % 20 \% 20% 的评测用例, n ≤ 10 n \leq 10 n10

对于 40 % 40 \% 40% 的评测用例, n ≤ 300 n \leq 300 n300

对于 60 % 60 \% 60% 的评测用例, n ≤ 5000 n \leq 5000 n5000;

对于 85 % 85 \% 85% 的评测用例, n ≤ 1 0 5 n \leq 10^{5} n105;

对于所有评测用例, 1 ≤ n ≤ 1 0 6 1 \leq n \leq 10^{6} 1n106

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/324907.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Linux:lesson1】的基本指令

&#x1f381;个人主页&#xff1a;我们的五年 &#x1f50d;系列专栏&#xff1a;Linux课程学习 &#x1f337;追光的人&#xff0c;终会万丈光芒 &#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐文章 目录 &#x1f697;打开Xshell&#xff0c;登陆root…

ASP.NET WebApi 如何使用 OAuth2.0 认证

前言 OAuth 2.0 是一种开放标准的授权框架&#xff0c;用于授权第三方应用程序访问受保护资源的流程。 OAuth 2.0 认证是指在这个框架下进行的身份验证和授权过程。 在 OAuth 2.0 认证中&#xff0c;涉及以下主要参与方&#xff1a; 资源所有者&#xff08;Resource Owner&…

springboot 引入第三方bean

如何进行第三方bean的定义 参数进行自动装配

PCB检查

文章目录 1、打开DRC2、database check3、检查DRC4、检查多余的线5、其他需要注意的点a.检查差分线、等长线是否已调好b.注意检查晶振、电感等元件上/下方是否其他线经过&#xff08;一般不允许线经过&#xff09;c.打开place_bound_top/bottom 检查元件是否超过这个允许范围d.…

【高校科研前沿】北师大陈晋教授团队在遥感顶刊发表最新成果:ClearSCD模型:在高空间分辨率遥感影像中综合利用语义和变化关系进行语义变化检测

01文章简介 论文名称&#xff1a;The ClearSCD model: Comprehensively leveraging semantics and change relationships for semantic change detection in high spatial resolution remote sensing imagery&#xff08;ClearSCD模型&#xff1a;在高空间分辨率遥感影像中综合…

【GESP】2023年12月图形化二级 -- 小杨报数

小杨报数 【题目描述】 小杨需要从 1 1 1到 N N N报数。在报数过程中&#xff0c;小杨希望跳过 M M M的倍数。例如&#xff0c;如果 N 5 N5 N5&#xff0c; M 2 M2 M2&#xff0c;那么小杨就需要依次报出 1 1 1&#xff0c; 3 3 3&#xff0c; 5 5 5。 默认小猫角色和白色背…

桥接模式类图与代码

欲开发一个绘图软件&#xff0c;要求使用不同的绘图程序绘制不同的图形。以绘制直线和圆形为例&#xff0c;对应的绘图程序如表 7.7 所示。 根据绘图软件的扩展性要求&#xff0c;该绘图软件将不断扩充新的图形和新的绘图程序。为了避免出现类爆炸的情况&#xff0c;现采用桥接…

车辆运动模型中LQR代码实现

一、前言 最近看到关于架构和算法两者关系的一个描述&#xff0c;我觉得非常认同&#xff0c;分享给大家。 1、好架构起到两个作用&#xff1a;合理的分解功能、合理的适配算法&#xff1b; 2、好的架构是好的功能的必要条件&#xff0c;不是充分条件&#xff0c;一味追求架构…

Scala编程入门:从零开始的完整教程

目录 引言环境准备创建第一个Scala项目基本语法高阶概念进阶资源结语 引言 Scala是一种强大的、静态类型的、多范式编程语言&#xff0c;它结合了面向对象和函数式编程的特点。本教程将指导您如何从零开始学习Scala&#xff0c;并搭建一个简单的开发环境。让我们开始探索Scala…

webassembly入门详解(C++)

一、环境配置 环境说明,操作系统为window操作系统。 1.1 下载和安装python 下载 需要python版本至少3.6版本 python下载地址:https://www.python.org/getit/ 安装 检测安装结果 win+R组合键->cmd->输入python->回车 1.2 下载和安装emsdk 下载 下载地址:https://gi…

春秋云镜 CVE-2022-4230

靶标介绍&#xff1a; WP Statistics WordPress 插件13.2.9之前的版本不会转义参数&#xff0c;这可能允许经过身份验证的用户执行 SQL 注入攻击。默认情况下&#xff0c;具有管理选项功能 (admin) 的用户可以使用受影响的功能&#xff0c;但是该插件有一个设置允许低权限用户…

Spring Security基础教程:从入门到实战

作者介绍&#xff1a;✌️大厂全栈码农|毕设实战开发&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。 推荐订阅精彩专栏 &#x1f447;&#x1f3fb; 避免错过下次更新 Springboot项目精选实战案例 更多项目&#xff1a;CSDN主页YAML墨韵 学如逆水行舟&#xff0c…

LOTO示波器动作编程功能(命令批处理)

动作编程功能是为了方便客户根据自己的应用场景&#xff0c;做到一个按键就连续做多个示波器操作&#xff0c;从而降低了对操作人员的技术要求&#xff0c;做到傻瓜式操作。之前LOTO有个类似的功能&#xff0c;是把示波器的基础设置根据不同的测试场景存成不同的设置文件&#…

新建的springBoot WEB项目无法自动返回html模版(gradle+kotlin版本)

最近研究了springBoot创建web项目&#xff0c; 第一步服务端返回字符串没有问题&#xff0c;第二步返回html时&#xff0c;还是返回的字符串。 文章目录 一、参考方案二、新建springBoot web项目三、启动项目的三种方式 一、参考方案 将控制器类的 RestController 改为 Contro…

基于CCS5.5的双音多频(DTMF)信号检测仿真实验(①检测型音频文件②输入生成音频并检测)

DTMF的优点 我们知道,DTMF根本上仍然是频谱分析,基础还是DFT,但DFT通常需要对一整段数据做变换,而DTMF不同,每输入一个采样点就计算一次,更有利于硬件实现。 基于CCS的双音多频(DTMF)信号检测原理 公式详细推导 详细的公式推导在下面这篇博客中已经进行了详细的描述,…

AI图书推荐:给自媒体创作者的ChatGPT使用指南

你是否厌倦了花费数小时盯着空白屏幕&#xff0c;努力为你的内容想出新鲜点子&#xff1f;想要将你的写作提升到下一个水平&#xff1f;有了ChatGPT&#xff0c;你可以告别写作障碍、无休止的修订和浪费的时间。 在这本全面的指南中&#xff0c;你将学到关于ChatGPT你需要知道…

vue3使用el-autocomplete请求远程数据

服务器端 RestController RequestMapping("/teacher") public class TeacherController {Resourceprivate TeacherService teacherService;GetMapping({"/v1/getTop10TeacherByName/","/v1/getTop10TeacherByName/{name}"})public ResultBean&l…

工业机器人应用实践之玻璃涂胶(篇二)

工业机器人 接上篇文章&#xff0c;浅谈一下实践应用&#xff0c;具体以玻璃涂胶为例&#xff1a; 了解工业机器人在玻璃涂胶领域的应用认识工具坐标系的标定方法掌握计时指令的应用掌握人机交互指令的应用掌握等待类指令用法&#xff08;WaitDI、WaitUnitl 等&#xff09;认…

【gpedit.msc】组策略编辑器的安装,针对windows家庭版,没有此功能

创建一个记事本文件然后放入以下内容 echo offpushd "%~dp0"dir /b %systemroot%\Windows\servicing\Packages\Microsoft-Windows-GroupPolicy-ClientExtensions-Package~3*.mum >gp.txtdir /b %systemroot%\servicing\Packages\Microsoft-Windows-GroupPolicy-…

进程间通信

文章目录 1.进程间通信2.进程间通信方式2.1 管道---匿名管道2.2 使用管道---管道测试接口(代码实现) 3.进程池3.1 进程池的原理图3.2 进程池的代码实现 4.命名管道4.1 有名管道通信4.2 有名管道通信的代码实现 5.共享内存5.1 共享内存原理5.2 共享内存的代码实现 6.共享内存7.代…