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

YLT C++ 4级 2022.03

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

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

编程题题号 #22393

分值 25

N5481 [CIE 202203 四级 T1] 拦截导弹

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于 $30000$ 的正整数），计算这套系统最多能拦截多少导弹。

输入格式

第一行是一个整数 $N$ （不超过 $15$ ），表示导弹数。第二行包含 $N$ 个整数，为导弹依次飞来的高度（雷达给出的高度数据是不大于 $30000$ 的正整数）。

输出格式

一个整数，表示最多能拦截的导弹数。

样例

样例 1
输入：

8
389 207 155 300 299 170 158 65

输出：

提示

无

编程题题号 #22394

分值 25

N5482 [CIE 202203 四级 T2] 神奇的数列

题目描述

一个正整数数列，可以将它切割成若干个数据段，每个数据段由值相同的相邻元素构成。该数列的神奇之处在于，每次切除一个数据段后，该数据段前后的元素自动连接在一起成为邻居。例如从数列 “ $2\ 8\ 9\ 77\ 6\ 9\ 4$ ” 中切除数据段 “ $7\ 7$ ” 后，余下的元素会构成数列 “ $2\ 8\ 9\ 6\ 94$ ”
请问若要将该数列切割成若干个数据段，则至少会切出来几个数据段？
样例：按下列顺序切割数列 “ $2\ 8\ 9\ 7\ 7\ 6\ 9\ 4$ ” ，只要切割成 $6$ 段
切割出 “ $7\ 7$ ” ，余下 “ $2\ 8\ 9\ 6\ 9\ 4$ ”
切割出 “ $6$ ” ，余下 “ $2\ 8\ 9\ 9\ 4$ ”
切割出 “ $9\ 9$ ” ，余下 “ $2\ 8\ 4$ ”
切割出 “ $2$ ” ，余下 “ $8\ 4$ ”
切割出 “ $8$ ” ，余下 “ $4$ ”

输入格式

第一行是一个整数，示共有多少组测试数据。每组测试数据的输入包括两行：第一行是整数 $N$ , $N\leq 200$ ,表示数列的长度，第二行是 $N$ 个正整数。

输出格式

每个测试案例的输出占一行，是一个整数。格式是： Case n: x
$n$ 是测试数据组编号， $x$ 是答案

样例

样例 1
输入：

2
8
2 8 9 7 7 6 9 4
16
2 8 9 7 7 6 9 4 4 2 8 4 2 7 6 9

输出：

Case 1: 6
Case 2: 11

提示

无

编程题题号 #22395

分值 25

N5483 [CIE 202203 四级 T3] 硬币

题目描述

宇航员 $Bob$ 有一天来到火星上，他有收集硬币的习惯。于是他将火星上所有面值的硬币都收集起来了，一共有 $n$ 种，每种只有一个：面值分别为 $a_1,a_2 \ldots a_n$ 。 $Bob$ 在机场看到了一个特别喜欢的礼物，想买来送给朋友 $Alice$ ，这个礼物的价格是 $X$ 元。 $Bob$ 很想知道为了买这个礼物他的哪些硬币是必须被使用的，即 $Bob$ 必须放弃收集好的哪些硬币种类。飞机场不提供找零，只接受恰好 $X$ 元。

输入格式

第一行包含两个正整数 $n$ 和 $x$ 。（ $1 \leq n \leq 200$ , $1 \leq x \leq 10000$ )
第二行从小到大为 $n$ 个正整数 $a_1, a_2, a_3 … a_n$ （ $1 \leq a_i \leq 10000$ )

输出格式

第一行是一个整数，即有多少种硬币是必须被使用的。
第二行是这些必须使用的硬币的面值（从小到大排列）。

样例

样例 1
输入：

5 18
1 2 3 5 10

输出：

2
5 10

提示

输入数据将保证给定面值的硬币中至少有一种组合能恰好能够支付 $X$ 元。如果不存在必须被使用的硬币，则第一行输出 $0$ ，第二行输出空行。

编程题题号 #22396

分值 25

N5484 [CIE 202203 四级 T4] 公共子序列

题目描述

我们称序列 $Z =$ 是序列 $X =$ 的子序列当且仅当存在严格上升的序列 $$，使得对 $j = 1, 2, ... ,k$ , 有 $x_{ij} = z_j$ 。比如 $Z =$ 是 $X =$ 的子序列。现在给出两个序列 $X$ 和 $Y$ ，你的任务是找到 $X$ 和 $Y$ 的最大公共子序列，也就是说要找到一个最长的序列 $Z$ ，使得 $Z$ 既是 $X$ 的子序列也是 $Y$ 的子序列。

输入格式

输入包括多组测试数据。每组数据包括一行，给出两个长度不超过 $200$ 的字符串，表示两个序列。两个字符串之间由 $1$ 个空格隔开。

输出格式

对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。

样例

样例 1
输入：

abcfbc abfcab
programming contest
abcd mnp

输出：

4
2
0

提示

无