理论卷2021年12月青少年软件编程(C\C++) · 四级

YLT C++ 4级 2021.12

满分 100 · 及格 60 · 时长 60 分钟 · 共 4 题 (编程题4)

试卷阅览 · 免费预览前 10 题 · 交卷后可查看答案与解析

编程题题号 #22397

分值 25

N5485 [CIE 202112 四级 T1] 移动路线

题目描述

桌子上有一个 $m$ 行 $n$ 列的方格矩阵，将每个方格用坐标表示，行坐标从下到上依次递增，列坐标从左至右依次递增，左下角方格的坐标为 $(1,1)$ ，则右上角方格的坐标为 $(m,n)$ 。
小明是个调皮的孩子，一天他捉来一只蚂蚁，不小心把蚂蚁的右脚弄伤了，于是蚂蚁只能向上或向右移动。小明把这只蚂蚁放在左下角的方格中，蚂蚁从左下角的方格中移动到右上角的方格中，每步移动一个方格。蚂蚁始终在方格矩阵内移动，请计算出不同的移动路线的数目。
对于 $1$ 行 $1$ 列的方格矩阵，蚂蚁原地移动，移动路线数为 $1$ ；对于 $1$ 行 $2$ 列（或 $2$ 行 $1$ 列）的方格矩阵，蚂蚁只需一次向右（或向上）移动，移动路线数也为 $1$ ……对于一个 $2$ 行 $3$ 列的方格矩阵，如下图所示：
$\left[ \begin{array} { l l l } { ( 2 , 1 ) } & { ( 2 , 2 ) } & { ( 2 , 3 ) } \\ { ( 1 , 1 ) } & { ( 1 , 2 ) } & { ( 1 , 3 ) } \end{array} \right]$
蚂蚁共有 $3$ 种移动路线：
路线 $1$ ： $(1,1)$ → $(1,2)$ → $(1,3)$ → $(2,3)$
路线 $2$ ： $(1,1)$ → $(1,2)$ → $(2,2)$ → $(2,3)$
路线 $3$ ： $(1,1)$ → $(2,1)$ → $(2,2)$ → $(2,3)$

输入格式

输入只有一行，包括两个整数 $m$ 和 $n$ $(0<m+n\leq 20)$ ，代表方格矩阵的行数和列数， $m$ 、 $n$ 之间用空格隔开

输出格式

输出只有一行，为不同的移动路线的数目。

样例

样例 1
输入：

2 3

输出：

提示

无

编程题题号 #22398

分值 25

N5486 [CIE 202112 四级 T2] 移动办公

题目描述

假设你经营着一家公司，公司在北京和南京各有一个办公地点。公司只有你一个人，所以你只能每月选择在一个城市办公。在第 $i$ 个月，如果你在北京办公，你能获得 $P_i$ 的营业额，如果你在南京办公，你能获得 $N_i$ 的营业额。但是，如果你某个月在一个城市办公，下个月在另一个城市办公，你需要支付 $M$ 的交通费。那么，该怎样规划你的行程（可在任何一个城市开始），才能使得总收入（总营业额减去总交通费）最大？

输入格式

输入的第一行有两个整数 $T$ $(1 \leq T \leq 100)$ 和 $M$ $(1 \leq M \leq 100)$ ， $T$ 代表总共的月数， $M$ 代表交通费。接下来的 $T$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$ ）的的整数，分别表示某个月在北京和在南京办公获得的营业额。

输出格式

输出只包括一行，这一行只包含一个整数，表示可以获得的最大总收入。

样例

样例 1
输入：

输出：

提示

无

编程题题号 #22399

分值 25

N5487 [CIE 202112 四级 T3] 最长公共子上升序列

题目描述

给定两个整数序列，写一个程序求它们的最长上升公共子序列。当以下条件满足的时候，我们将长度为 $N$ 的序列 $S_1 , S_2 . . . S_N$ 称为长度为 $M$ 的序列 $A_1 , A_2 , . . . , A_M$ 的上升子序列：存在 $1 \leq i_1 < i_2 < . . . < i_N \leq M$ ，使得对所有 $1 \leq j \leq N$ ，均有 $S_j = A_{ij}$ ，且对于所有的 $1 \leq j < N$ ，均有 $S_j < S_{j+1}$ 。

输入格式

每个序列用两行表示，第一行是长度 $M$ $(1 \leq M \leq 500)$ ，第二行是该序列的 $M$ 个整数 $A_i$ $(-2^{31} \leq A_i < 2^{31} )$

输出格式

在第一行，输出两个序列的最长上升公共子序列的长度 $L$ 。在第二行，输出该子序列。如果有不止一个符合条件的子序列，则输出任何一个即可。

样例

样例 1
输入：

5
1 4 2 5 -12
4
-12 1 2 4

输出：

2
1 4

提示

无

编程题题号 #22400

分值 25

N5488 [CIE 202112 四级 T4] 技能树

题目描述

设二叉树中每个节点的子节点数为 $0$ 或 $2$ ，求有 $N$ 个节点高度为 $M$ 的不同的二叉树有多少个
(输出 $\mod 9901$ 后的结果)。

输入格式

两个空格分开的整数, $N$ 和 $K$ 。

输出格式

第 $1$ 行: 一个整数，表示可能的技能树的个数除以 $9901$ 的余数。

样例

样例 1
输入：

5 3

输出：

提示

有 $5$ 个节点，高为 $3$ 的两个不同的技能树。约定: $n$ 在 $[3,300]$ 间, $m$ 在 $(1,100)$ 间