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

YLT C++ 4级 2022.06

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

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

编程题题号 #22389

分值 25

N5477 [CIE 202206 四级 T1] 公共子序列

题目描述

我们称序列 $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

提示

无

编程题题号 #22390

分值 25

N5478 [CIE 202206 四级 T2] 硬币问题

题目描述

有 $N$ （不大于 $100$ ）种硬币，编号为 $1$ 至 $N$ ，已知每种硬币的重量（不超过 $100$ 的正整数）和面额（不超过 $100$ 的正整数），每种硬币数量不限。选取总重量不超过 $C$ （不大于 $1000$ 的正整数）的硬币，最多能获得多少总面额？

输入格式

第一行输入 $N$ 第二行输入 $C$ 第三行输入各硬币重量，用空格隔开第四行输入各硬币价值，用空格隔开

输出格式

最大总面额

样例

样例 1
输入：

输出：

提示

无

编程题题号 #22391

分值 25

N5479 [CIE 202206 四级 T3] 田忌赛马

题目描述

你一定听过田忌赛马的故事吧？
如果 $3$ 匹马变成 $1000$ 匹，齐王仍然让他的马按从优到劣的顺序出赛，田忌可以按任意顺序选择他的赛马出赛。赢一局，田忌可以得到 $200$ 两银子，输一局，田忌就要输掉 $200$ 两银子，平局的话不输不赢。
请问田忌最多能赢多少银子?

输入格式

输入包含多组测试数据. 每组测试数据的第一行是一个整数 $n(1\leq n\leq 1000)$ ,表示田忌和齐王都拥有 $n$ 匹马。接下来一行是 $n$ 个整数，表示田忌的马的速度，下一行也是 $n$ 个整数，表示齐王的马的速度。输入的最后以一个 $0$ 表示结束。

输出格式

对每组数据，输出一个整数，表示田忌至多可以赢多少银子，如果田忌赢不了，就输出一个负数，表示田忌最少要输多少银子。

样例

样例 1
输入：

输出：

200
0
0

提示

无

编程题题号 #22392

分值 25

N5480 [CIE 202206 四级 T4] 上机

题目描述

又到周末了，同学们陆陆续续开开心心的来到机房上机。 $jbr$ 也不例外，但是他到的有点晚，发现有些机位上已经有同学正在做题，有些机位还空着。细心的 $jbr$ 发现，一位同学来到机房，坐在机位 $i$ 上，如果他的左右两边都空着，他将获得能力值 $a[i]$ ；如果当他坐下时，左边或者右边已经有一个人在上机了，他将获得能力值 $b[i]$ ；如果当他坐下时，他的左边右边都有人在上机，他将获得能力值 $c[i]$ 。
同时他发现，已经在上机的同学不会受到刚要坐下的同学的影响，即他们的能力值只会在坐下时产生，以后不会发生变化;第一个机位左边没有机位，最后一个机位右边没有机位，无论何时坐在这两个机位上将无法获得 $c$ 值。
这时 $jbr$ 发现有一排机器还空着，一共有 $N$ 个机位，编号 $1$ 到 $N$ 。这时有 $N$ 位同学们陆陆续续来到机房，一个一个按照顺序坐在这排机位上。聪明的 $jbr$ 想知道怎么安排座位的顺序，可以使这 $N$ 位同学获得能力值的和最大呢？

输入格式

第一行一个整数 $N(1\leq N \leq 10000)$
第二行 $N$ 个数，表示 $a[i]$
第三行 $N$ 个数，表示 $b[i]$
第四行 $N$ 个数，表示 $c[i]$
$(1\leq a[i],b[i],c[i] \leq 10000)$

输出格式

一个整数，表示获得最大的能力值和

样例

样例 1
输入：

输出：

提示

第一位同学坐在第四个机位上，获得能力值 $4$ ；第二位同学坐在第三个机位上，获得能力值 $3$ ；第三位同学坐在第二个机位上，获得能力值 $3$ ；第四位同学坐在第一个机位上，获得能力值 $4$ ；总和为 $14$ 。