[Java知识库]第十三届蓝桥杯大赛软件赛决赛（Java 大学A组）

试题 A: 火柴棒数字

本题总分：$5$ 分

【问题描述】

??小蓝最近迷上了用火柴棒拼数字字符，方法如下图所示$：$

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

【答案提交】

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

9999999999777777777755555555554444444444333333333322222222221111111111

多重背包

??将数字视作价值为 $1$ 且各有 $10$ 个的物品，需要的火柴棒视作其重量，这显然是个多重背包问题。

??不采用滚动数组以便还原组合方案，在还原方案的时候优先输出尽可能多的，值较大的数字即可。

public class Test {

	public static void main(String[] args) { new Test().run(); }
	
	int N = 300, W[] = { 0,6,2,5,5,4,5,6,3,7,6 };
	
	void run() {
		int[][] dp = new int[11][N + 1];
		for (int i = 1; i <= 10; ++i)
			for (int k = 0; k <= 10; ++k)
				for (int j = k * W[i]; j <= 300; ++j)
					dp[i][j] = max(dp[i][j], dp[i - 1][j - k * W[i]] + k);
		for (int i = 10, j = 300, k = 0; i > 0; --i, k = 0) {
			for (int g = 1; g <= 10 && j - g * W[i] >= 0; ++g)
				if (dp[i][j] <= dp[i - 1][j - g * W[i]] + g) k = g;
			for (j -= k * W[i]; k > 0; --k) System.out.print(i - 1);
		}
	}
	
	int max(int arg1, int arg2) { return arg1 > arg2 ? arg1 : arg2; }
}

试题 B: 小蓝与钥匙

本题总分：$5$ 分

【问题描述】

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

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

【答案提交】

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

1286583532342313400

组合数学

??$28$ 个孩子中，任选 $14$ 个孩子拿到自己房间钥匙的组合数乘以第 $14$ 个错位排列数，即 $C_{28}^{14}\times D_{14}$ 就是我们所要提交的答案。

public class Test {

    public static void main(String[] args) { new Test().run(); }

    void run() { System.out.println(C(28, 14) * D(14)); }

    long C(int n, int m) {
        if (m > n || n < 0) return 0;
        if (n == m) return 1;
        return C(n - 1, m) + C(n - 1, m - 1);
    }

    long D(int n) {
        if (n == 1) return 0;
        if (n == 2) return 1;
        return (n - 1) * (D(n - 1) + D(n - 2));
    }
}

试题 C: 内存空间

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

【问题描述】

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

??为了简化问题，变量的类型只有以下三种：

??$\mathrm{i}\mathrm{n}\mathrm{t}：$整型变量，一个 $\mathrm{i}\mathrm{n}\mathrm{t}$ 型变量占用 $4\mathrm{B}\mathrm{y}\mathrm{t}\mathrm{e}$ 的内存空间。
??$\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}：$长整型变量，一个 $\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}$ 型变量占用 $8\mathrm{B}\mathrm{y}\mathrm{t}\mathrm{e}$ 的内存空间。
??$\mathrm{S}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{n}\mathrm{g}：$字符串变量，占用空间和字符串长度有关，设字符串长度为 $L$，则字符串占用 $L\mathrm{B}\mathrm{y}\mathrm{t}\mathrm{e}$ 的内存空间，如果字符串长度为 $0$ 则占用 $0\mathrm{B}\mathrm{y}\mathrm{t}\mathrm{e}$ 的内存空间。

??定义变量的语句只有两种形式，第一种形式为$：$

$\mathrm{t}\mathrm{y}\mathrm{p}\mathrm{e}\mathrm{v}\mathrm{a}\mathrm{r}1=\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}1,\mathrm{v}\mathrm{a}\mathrm{r}2=\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}2?;$

??定义了若干个 $\mathrm{t}\mathrm{y}\mathrm{p}\mathrm{e}$ 类型变量 $\mathrm{v}\mathrm{a}\mathrm{r}1$、$\mathrm{v}\mathrm{a}\mathrm{r}2$、$?$，并且用 $\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}1$、$\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}2?$ 初始化，

??多个变量之间用 $’,’$ 分隔，语句以 $’;’$ 结尾，$\mathrm{t}\mathrm{y}\mathrm{p}\mathrm{e}$ 可能是 $\mathrm{i}\mathrm{n}\mathrm{t}$、$\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}$ 或 $\mathrm{S}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{n}\mathrm{g}$。例如 $\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{a}=1,\mathrm{b}=5,\mathrm{c}=6;$ 占用空间为 $12\mathrm{B}\mathrm{y}\mathrm{t}\mathrm{e}$；$\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}\mathrm{a}=1,\mathrm{b}=5;$ 占用空间为 $16\mathrm{B}\mathrm{y}\mathrm{t}\mathrm{e}$；$\mathrm{S}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{s}1=””,\mathrm{s}2=”\mathrm{h}\mathrm{e}\mathrm{l}\mathrm{l}\mathrm{o}”,\mathrm{s}3=”\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{l}\mathrm{d}”;$ 占用空间为 $10\mathrm{B}\mathrm{y}\mathrm{t}\mathrm{e}$。

??第二种形式为$：$

$\mathrm{t}\mathrm{y}\mathrm{p}\mathrm{e}[]\mathrm{a}\mathrm{r}\mathrm{r}1=\mathrm{n}\mathrm{e}\mathrm{w}\mathrm{t}\mathrm{y}\mathrm{p}\mathrm{e}[\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}1],\mathrm{a}\mathrm{r}\mathrm{r}2=\mathrm{n}\mathrm{e}\mathrm{w}\mathrm{t}\mathrm{y}\mathrm{p}\mathrm{e}[\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}2]?;$

??定义了若干 $\mathrm{t}\mathrm{y}\mathrm{p}\mathrm{e}$ 类型的一维数组变量 $\mathrm{a}\mathrm{r}\mathrm{r}1$、$\mathrm{a}\mathrm{r}\mathrm{r}2?$，且数组的大小为 $\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}1$、$\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}2?$，多个变量之间用 $’,’$ 进行分隔，语句以 $’;’$ 结尾，$\mathrm{t}\mathrm{y}\mathrm{p}\mathrm{e}$ 只可能是 $\mathrm{i}\mathrm{n}\mathrm{t}$ 或 $\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}$。例如 $\mathrm{i}\mathrm{n}\mathrm{t}[]\mathrm{a}1=\mathrm{n}\mathrm{e}\mathrm{w}\mathrm{i}\mathrm{n}\mathrm{t}[10];$ 占用的内存空间为 $40\mathrm{B}\mathrm{y}\mathrm{t}\mathrm{e}$；$\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}[]\mathrm{a}1=\mathrm{n}\mathrm{e}\mathrm{w}\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}[10],\mathrm{a}2=\mathrm{n}\mathrm{e}\mathrm{w}\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}[10];$ 占用的内存空间为 $160\mathrm{B}\mathrm{y}\mathrm{t}\mathrm{e}$。

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

【输入格式】

??输入的第一行包含一个整数 $T$ ，表示有 $T$ 句变量定义的语句。

??接下来 $T$ 行，每行包含一句变量定义语句。

【输出格式】

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

【样例输入 1】

1
long[] nums=new long[131072];

【样例输出 1】

1MB

【样例输入 2】

4
int a=0,b=0;
long x=0,y=0;
String s1="hello",s2="world";
long[] arr1=new long[100000],arr2=new long[100000];

【样例输出 2】

1MB538KB546B

【样例说明】
?样例 $1$，占用的空间为 $131072\times 8=1048576\mathrm{B}$，换算过后正好是 $1\mathrm{M}\mathrm{B}$，其 它三个单位 $\mathrm{G}\mathrm{B}$、$\mathrm{K}\mathrm{B}$、$\mathrm{B}$ 前面的数字都为 $0$ ，所以不用输出。
?样例 $2$，占用的空间为 $4\times 2+8\times 2+10+8\times 100000\times 2B$，换算后是 $1\mathrm{M}\mathrm{B}538\mathrm{K}\mathrm{B}546\mathrm{B}$。

【评测用例规模与约定】

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

// 大模拟

试题 D: 斐波那契数组

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

【问题描述】

??如果数组 $A=(a_0,a_1,?,a_{n?1})$ 满足以下条件，就说它是一个斐波那契数组$：$

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

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

【输入格式】

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

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

【输出格式】

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

【样例输入】

5
1 2 2 4 8

【样例输出】

3

【样例说明】
?将原数组修改为 $(1,1,2,3,5)$，最少修改三个元素变成了一个斐波那契数组。

【评测用例规模与约定】

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

??首先，$F_{31}>1e6$，而 $1\le a_i\le 10^6$，于是无论 $a_0,a_1$ 取哪个正整数，从 $A$ 的第 $30$ 项开始，所有的元素都需要修改，

??同时，令 $G$ 为 $G_1=G_2=g$ 的 “广义斐波那契数列”（这个名词其实已经被定义了），观察 $F$ 与 $G$ 各项$:$

??$G_1=g{F}_1$
??$G_2=g{F}_2$
??$G_3=g{F}_1+g{F}_2=g(F_1+F_2)=g{F}_3$
??$?$
??$G_n=g(F_{n?1}+F_{n?2})=g{F}_n$

??于是我们只需统计 $A$ 中，与 $F$ 比值出现频率最高的项集，然后将其的补集替换为对应的 “广义斐波那契数列” 就行了。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.IOException;
import java.util.TreeMap;
import java.util.Map;

public class Main {
	
	public static void main(String[] args) { new Main().run(); }
	
	double[] fib = { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040 };
	
	void run() {
		Map<Double, Integer> map = new TreeMap();
		int n = nextInt(), m = 0, a, ans = n;
		if (n > 30) n = 30;
		for (int i = 0; i < n; ++i) {
			a = nextInt();
			map.put(a / fib[i], map.getOrDefault(a / fib[i], 0) + 1);
		}
		for (Map.Entry<Double, Integer> entry : map.entrySet())
			m = Math.max(m, entry.getValue());
		System.out.print(ans - m);
	}
	
	StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	
	int nextInt() {
		try {
			in.nextToken();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return (int)in.nval;
	}
}

试题 E: 交通信号

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

【问题描述】

??$\mathrm{L}\mathrm{Q}$ 市的交通系统可以看成由 $n$ 个结点和 $m$ 条有向边组成的有向图。在每条边上有一个信号灯，会不断按绿黄红黄绿黄红黄… 的顺序循环 (初始时刚好变到绿灯)。当信号灯为绿灯时允许正向通行，红灯时允许反向通行，黄灯时不允许通行。每条边上的信号灯的三种颜色的持续时长都互相独立，其中黄灯的持续时长等同于走完路径的耗时。当走到一条边上时，需要观察边上的信号灯，如果允许通行则可以通过此边，在通行过程中不再受信号灯的影响；否则需要等待，直到允许通行。 请问从结点 $s$ 到结点 $t$ 所需的最短时间是多少，如果 $s$ 无法到达 $t$ 则输出 $?1$。

【输入格式】

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

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

【输出格式】

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

【样例输入】

4 4 1 4
1 2 1 2 6
4 2 1 1 5
1 3 1 1 1
3 4 1 99 1

【样例输出】

11

【评测用例规模与约定】

??对于 $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{M}\mathrm{B}$?本题总分：$15$ 分

【问题描述】

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

??形式化描述为$：$ $$b_i=?\begin{array}{ll}\max (a_{n?1},a_0,a_1),& (i=1);\\ \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).\end{array}$$??小蓝想知道，可能有多少个满足条件的数组 $A$，经过一次相邻最大化操作后能得到数组 $B$，注意 $A$ 中的每个元素都要求为非负整数。

【输入格式】

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

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

【输出格式】

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

【样例输入】

5
8 6 1 8 8

【样例输出】

7

【样例说明】
??可能的 $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$。

分类讨论

??任取 $B$ 中 $2$ 个连续的元素 $b_i,b_{i+1}$，

??若 $b_i<b_{i+1}$，能确定 $a_{i+2}=b_{i+1}$，$a_{i?1},a_i,a_{i+1}$ 中存在一个 $b_i$ 且都小于等于 $b_i$。

??若 $b_i>b_{i+1}$，能确定 $a_{i?1}=b_i$，$a_i,a_{i+1},a_{i+2}$ 中存在一个 $b_{i+1}$ 且都小于等于 $b_{i+1}$。

??若 $b_i=b_{i+1}$，能确定 $a_{i?1},a_i,a_{i+1},a_{i+2}$ 中存在一个 $b_i$ 且都小于等于 $b_i$。

试题 G: 六六大顺

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

【问题描述】

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

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

??定义一个数列 $B=(b_1,b_2,?,b_i,?)$，其中 $b_1 = $6\times 6,b_2=66\times 66,?,b_i=a_i?a_i$。

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

【输入格式】

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

【输出格式】

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

【样例输入】

3

【样例输出】

447948

【样例说明】
??$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$。

试题 H: 选素数

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

【问题描述】

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

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

【输入格式】

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

【输出格式】

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

【样例输入】

22

【样例输出】

8

【评测用例规模与约定】

??对于 $60\%$ 的评测用例，$1\le n\le 5000$；
??对于所有评测用例，$1\le n\le 10^6$。

试题 ?I: 图书借阅

时间限制: $10.0\mathrm{s}$?内存限制: $1.0\mathrm{G}\mathrm{B}$?本题总分：$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,?,a_n$，相邻两个整数之间用一个空格分隔，表示目前拥有的每种书的本数。

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

【输出格式】

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

【样例输入】

3 11 3
1 0 2
1 2 4
1 1 2
1 4 5
1 3 5
1 1 3
2 1 1
2 2 2
2 3 3
2 1 2
2 3 4
3 1 5

【样例输出】

10

【评测用例规模与约定】

??对于 $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$。

试题 J: 括号序列树

时间限制: $5.0\mathrm{s}$?内存限制: $512.0\mathrm{M}\mathrm{B}$?本题总分：$25$ 分

【问题描述】

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

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

【输入格式】

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

【输出格式】

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

【样例输入】

9

【样例输出】

10350

【评测用例规模与约定】

??对于 $20\%$ 的评测用例，$n\le 10$；
??对于 $40\%$ 的评测用例，$n\le 300$；
??对于 $60\%$ 的评测用例，$n\le 5000$；
??对于 $85\%$ 的评测用例，$n\le 10^5$；
??对于所有评测用例，$1\le n\le 10^6$。