2022.06全国青少年软件编程（C语言）等级考试试卷（四级）

青少年软件编程（C语言）等级考试试卷（四级） 分数：100 题数：4 一、编程题(共4题，共100分) 1. 公共子序列 我们称序列Z = < z1, z2, ..., zk >是序列X = < x1, x2, ..., xm >的子序列当且仅当存在 严格上升 的序列< i1, i2, ..., ik >，使得对j = 1, 2, ... ,k, 有xij = zj。比如Z = < a, b, f, c > 是X = < a, b, c, f, b, c >的子序列。 现在给出两个序列X和Y，你的任务是找到X和Y的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z既是X的子序列也是Y的子序列。 时间限制：3000 内存限制：65536 输入 输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200的字符串，表示两个序列。两个字符串之间由若干个空格隔开。 输出 对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。 样例输入 abcfbc abfcab programming contest abcd mnp 样例输出 4 2 0 试题编号：20220618_4_01 试题类型：编程题 标准答案： 试题难度：一般 试题解析： 展示地址：点击浏览 考生答案： 考生得分：0 是否评分：已评分 评价描述： 2. 硬币问题 有N（不大于100）种硬币，编号为1至N，已知每种硬币的重量（不超过100的正整数）和面额（不超过100的正整数），每种硬币数量不限。选取总重量不超过C（不大于1000的正整数）的硬币，最多能获得多少总面额？ 时间限制：1000 内存限制：65536 输入 第一行输入N 第二行输入C 第三行输入各硬币重量，用空格隔开 第四行输入各硬币价值，用空格隔开 输出 最大总面额 样例输入 3 5 1 2 5 1 3 6 样例输出 7 试题编号：20220618_4_02 试题类型：编程题 标准答案： 试题难度：一般 试题解析： 展示地址：点击浏览 考生答案：（此题已作答） 考生得分：0 是否评分：已评分 评价描述： 3. 田忌赛马 你一定听过田忌赛马的故事吧？ 如果3匹马变成1000匹，齐王仍然让他的马按从优到劣的顺序出赛，田忌可以按任意顺序选择他的赛马出赛。赢一局，田忌可以得到200两银子，输一局，田忌就要输掉200两银子，平局的话不输不赢。 请问田忌最多能赢多少银子? 时间限制：5000 内存限制：65536 输入 输入包含多组测试数据. 每组测试数据的第一行是一个整数n(1<=n<=1000),表示田忌和齐王都拥有n匹马。接下来一行是n个整数，表示田忌的马的速度，下一行也是n个整数，表示齐王的马的速度。 输入的最后以一个0表示结束。 输出 对每组数据，输出一个整数，表示田忌至多可以赢多少银子，如果田忌赢不了，就输出一个负数，表示田忌最少要输多少银子。 样例输入 3 92 83 71 95 87 74 2 20 20 20 20 2 20 19 22 18 0 样例输出 200 0 0 试题编号：20220618_4_03 试题类型：编程题 标准答案： 试题难度：一般 试题解析： 展示地址：点击浏览 考生答案： 考生得分：0 是否评分：已评分 评价描述： 4. 上机 又到周末了，同学们陆陆续续开开心心的来到机房上机。jbr也不例外，但是他到的有点晚，发现有些机位上已经有同学正在做题，有些机位还空着。细心的jbr发现，一位同学来到机房，坐在机位i上，如果他的左右两边都空着，他将获得能力值a[i]；如果当他坐下时，左边或者右边已经有一个人在上机了，他将获得能力值b[i]；如果当他坐下时，他的左边右边都有人在上机，他将获得能力值c[i]。 同时他发现，已经在上机的同学不会受到刚要坐下的同学的影响，即他们的能力值只会在坐下时产生，以后不会发生变化;第一个机位左边没有机位，最后一个机位右边没有机位，无论何时坐在这两个机位上将无法获得c值。 这时jbr发现有一排机器还空着，一共有N个机位，编号1到N。这时有N位同学们陆陆续续来到机房，一个一个按照顺序坐在这排机位上。聪明的jbr想知道怎么安排座位的顺序，可以使这N位同学获得能力值的和最大呢？ 时间限制：1000 内存限制：65536 输入 第一行一个整数N(1<= N <= 10000) 第二行N个数，表示a[i] 第三行N个数，表示b[i] 第四行N个数，表示c[i] (1<= a[i],b[i],c[i] <=10000) 输出 一个整数，表示获得最大的能力值和 样例输入 4 1 2 2 4 4 3 3 1 2 1 1 2 样例输出 14 提示 第一位同学坐在第四个机位上，获得能力值4； 第二位同学坐在第三个机位上，获得能力值3； 第三位同学坐在第二个机位上，获得能力值3； 第四位同学坐在第一个机位上，获得能力值4； 总和为14。 试题编号：20220618_4_04 试题类型：编程题 标准答案： 试题难度：一般 试题解析： 展示地址：点击浏览 考生答案： 考生得分：0 是否评分：已评分 评价描述： 学科网（北京）股份有限公司 $$