YLT C++ 4级 2021.09

N5489 [CIE 202109 四级 T1] 最佳路径

题目描述

如下所示的由正整数数字构成的三角形:

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。
注意：路径上的每一步只能从一个数走到下一层上和它最近的下边（正下方）的数或者右边（右下方）的数。

输入格式

第一行为三角形高度 $100\geq h\geq1$，同时也是最底层边的数字的数目。 从第二行开始，每行为三角形相应行的数字，中间用空格分隔。

输出格式

最佳路径的长度数值。

样例

样例 1
输入：

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出：

30

提示

无

N5490 [CIE 202109 四级 T2] 数字构造

题目描述

火山宝打算造一个 $n$ 位的十进制数字出来。
对于 $1$ 到 $n$ 中的每一个 $i$，火山宝可以从 $x_{i,1}, ..., x_{i,ki}$ 这 $k_i$ 个 $0-9$ 的数字中选择一个作为 $a_i$。
在选择结束后，$a_1a_2...a_n$ 形成了一个 $n$ 位的十进制数——这就是火山宝造出来的数。
你需要帮火山宝计算他能造出的数中，有多少个是 $3$ 的倍数。

输入格式

第一行输入一个整数 $n(1 \leq n \leq 18)$，表示数字的位数。 接下来 $n$ 行，每行第一个整数 $k_i (1 \leq k_i \leq 10)$，表示第 $i$ 中候选的数字数量。接着是 $k_i$ 个两两不同的 $0-9$ 范围内的数字 $x_{i,1}, ..., x_{i,ki}$。 输入保证 $0$ 不是第一位的可选项。

输出格式

你需要输出一行一个整数，表示火山宝能造出的数字中，$3$ 的倍数的数量。

样例

样例 1
输入：

2
5 5 6 7 8 9
5 0 1 2 3 4

输出：

9

样例 2
输入：

5
9 1 2 3 4 5 6 7 8 9
10 0 1 2 3 4 5 6 7 8 9
10 0 1 2 3 4 5 6 7 8 9
10 0 1 2 3 4 5 6 7 8 9
10 0 1 2 3 4 5 6 7 8 9

输出：

30000

提示

样例 $1$ 能造出来的 $3$ 的倍数有 $51, 54,60,63,72,81,84,90, 93$。

N5491 [CIE 202109 四级 T3] 奶牛散步

题目描述

从一个无限大的矩阵的中心点出发，一步只能向右走、向上走或向左走。恰好走 $N$ 步且不经过已走的点共有多少种走法？

输入格式

一个数字，代表 $N$,$N\leq 1000$

输出格式

输出有多少方案数,答案模 $12345$

样例

样例 1
输入：

2

输出：

7

提示

无

N5492 [CIE 202109 四级 T4] 吃奶酪

题目描述

$Jerry$ 准备偷吃 $Tom$ 的奶酪。所有的奶酪排成了一条直线，每块奶酪都有不同的美味程度。然而，如果有相邻两块奶酪都被 $Jerry$ 偷吃，$Tom$ 就会发现这一点并迅速抓住 $Jerry$。$Jerry$ 当然希望在不被 $Tom$ 发现的条件下吃到的奶酪美味度总和最大。当然，他也可以选择一块奶酪都不吃。请你帮助他规划一下偷吃的方案，告诉他最多能偷吃到多少的美味度吧。

输入格式

第一行一个整数 $T$ $(T\leq 100)$，表示测试数据组数。 接下来，每组测试数据包含两行。其中，第一行一个整数 $n$ $(1 \leq n \leq 100,000)$ ，表示奶酪的数量；第二行 $n$ 个整数，表示这一排直线上奶酪的美味程度，请注意，美味度保证能够被 $int$ 类型存储，且可能是负数。

输出格式

对于每组测试数据，输出一个整数，表示 $Jerry$ 可以吃到的最大美味度总和。请注意，美味度总和可能超过 $int$ 存储范围

样例

样例 1
输入：

2
4
1 2 3 1
5
2 7 9 3 1

输出：

4
12

提示

无