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

YLT C++ 4级 2024.03

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

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

编程题题号 #22369

分值 25

N5473 [CIE 202209 四级 T1] 最长上升子序列

题目描述

一个数的序列 $b_i$ ，当 $b_1 < b_2 < … < b_S$ 的时候，我们称这个序列是上升的。对于给定的一个序列 $(a_1, a_2, …, a_N)$ ，我们可以得到一些上升的子序列 $(ai_1, ai_2, …, ai_K)$ ，这里 $1 \leq i_1 < i_2 < … < i_K \leq N$ 。比如，对于序列 $(1, 7, 3, 5, 9, 4, 8)$ ，有它的一些上升子序列，如 $(1, 7)$ , $(3, 4, 8)$ 等等。这些子序列中最长的长度是 $4$ ，比如子序列 $(1, 3, 5, 8)$ . 你的任务，就是对于给定的序列，求出最长上升子序列的长度。

输入格式

输入的第一行是序列的长度 $N$ $(1 \leq N \leq 1000)$ 。
第二行给出序列中的 $N$ 个整数，这些整数的取值范围都在 $0$ 到 $10000$ 。

输出格式

最长上升子序列的长度。

样例

样例 1
输入：

7
1 7 3 5 9 4 8

输出：

提示

无

编程题题号 #22370

分值 25

N5498 [CIE 202103 四级 T2] 重启系统

题目描述

小明帮助管理一个处理数据的计算系统，有 $N$ 个待处理的任务，需要按照顺序来完成这些任务，即每次所完成任务的编号都要大于前一个完成任务的编号，且单个任务不可以分解完成。计算系统运行着一个奇怪的保护程序，它限制了系统当前所能处理的数据量不能超过上次完成任务所处理的数据量。重启系统可以使它立刻恢复到最高性能（一开始系统拥有最高性能，最高性能大于任何待处理任务的数据量）。小明有一次重启系统的权限（也可以不使用），你能帮他算出最多能完成几个任务吗？

输入格式

第一行： $N$ $(2 \leq N \leq 1000)$ 待处理的任务数第二行： $N$ 个整数，每个任务的数据量

输出格式

输出只包括一行，这一行只包含一个整数，表示最多能完成的任务数。

样例

样例 1
输入：

10
1 5 4 3 2 10 9 8 7 6

输出：

提示

回想一下最长上升子序列问题

编程题题号 #22371

分值 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$ ，第二行输出空行。

编程题题号 #22372

分值 25

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

题目描述

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

输入格式

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

输出格式

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

样例

样例 1
输入：

输出：

提示

无