首页 › 试卷 › C/C++编程考级 › C/C++编程四级 › 青少年软件编程(C语言四级)等级考试真题试卷(2022年6月)

青少年软件编程(C语言四级)等级考试真题试卷(2022年6月) VIP

C/C++编程四级 共 4 题 2022 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、简答题

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
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; #include &lt;string&gt; using namespace std; int f[1000][1000]; int main() {   string a, b;   while (cin &gt;&gt; a &gt;&gt; b) {     int n = a.size();     int m = b.size();     memset(f, 0, sizeof(f));     for (int i = 1; i &lt;= n; i++) {       for (int k = 1; k &lt;= m; k++) {         if (a[i - 1] == b[k - 1]) {           f[i][k] = max(f[i][k], f[i - 1][k - 1] + 1);         } else {           f[i][k] = max(f[i][k - 1], f[i - 1][k]);         }       }     }     cout &lt;&lt; f[n][m] &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。
2. 简答题

硬币问题

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

时间限制:1000

内存限制:65536

输入

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

输出

最大总面额

样例输入

3
5
1 2 5
1 3 6

样例输出

7
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int t[105], v[105]; int dp[1005]; int main() {   int n, c;   cin &gt;&gt; n &gt;&gt; c;   for (int i = 1; i &lt;= n; i++)     cin &gt;&gt; t[i];   for (int i = 1; i &lt;= n; i++)     cin &gt;&gt; v[i];   for (int i = 1; i &lt;= n; i++) {     for (int j = t[i]; j &lt;= c; j++) {       dp[j] = max(dp[j], dp[j - t[i]] + v[i]);     }   }   cout &lt;&lt; dp[c];   return 0; }</pre>
这道题暂未补解析。
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
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int h1, h2, t1, t2, n, i, ans = 0; int t[100001], k[100001]; int cmp(int a, int b) { return a &gt; b; } int main() {   while (cin &gt;&gt; n &amp;&amp; n) {     for (i = 1; i &lt;= n; i++)       cin &gt;&gt; t[i];     for (i = 1; i &lt;= n; i++)       cin &gt;&gt; k[i];     sort(t + 1, t + n + 1, cmp);     sort(k + 1, k + n + 1, cmp);     h1 = h2 = 1;     t1 = t2 = n;     while (h1 &lt;= t1) {       if (t[h1] &gt; k[h2])         ans += 200, h1++, h2++;       else {         if (t[h1] &lt; k[h2])           ans -= 200, t1--, h2++;         else {           if (t[t1] &gt; k[t2])             ans += 200, t1--, t2--;           else {             if (t[t1] &lt; k[h2])               ans -= 200;             t1--, h2++;           }         }       }     }     cout &lt;&lt; ans &lt;&lt; endl;     ans = 0;   } }</pre>
这道题暂未补解析。
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。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;cmath&gt; #include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; int a[10005]; int b[10005]; int c[10005]; int d     [10005]     [4]; // 考虑前i的座位已经坐好的前i个座位最大值,0-第i个人坐下的时候两边没人,1-左边有人,2-右边有人,3-都有人 int main() {   int n;   cin &gt;&gt; n;   int i;   for (i = 1; i &lt;= n; i++)     cin &gt;&gt; a[i];   for (i = 1; i &lt;= n; i++)     cin &gt;&gt; b[i];   for (i = 1; i &lt;= n; i++)     cin &gt;&gt; c[i];   d[1][0] = a[1];   d[1][2] = b[1];   for (i = 2; i &lt;= n; i++) {     d[i][0] =         max(d[i - 1][3], d[i - 1][2]) +         a[i]; // 第i个位置坐下的时候两边没人,要求它先于第i-1个人被坐,也就是说第i-1个人坐下的时候一定是右边有人     d[i][1] = max(d[i - 1][0], d[i - 1][1]) + b[i];     d[i][2] = max(d[i - 1][3], d[i - 1][2]) + b[i];     d[i][3] = max(d[i - 1][0], d[i - 1][1]) + c[i];   }   cout &lt;&lt; max(d[n][0], d[n][1]);   return 0; }</pre><pre class="brush:cpp;toolbar:false">// 参考答案2 #include &lt;bits/stdc++.h&gt; using namespace std; const int INF = 0x3f3f3f3f; const int N = 10000 + 1; int a[N], b[N], c[N], dp[N][4]; int main() {   int n;   scanf("%d", &amp;n);   for (int i = 1; i &lt;= n; i++)     scanf("%d", &amp;a[i]);   for (int i = 1; i &lt;= n; i++)     scanf("%d", &amp;b[i]);   for (int i = 1; i &lt;= n; i++)     scanf("%d", &amp;c[i]);   dp[1][0] = a[1];   dp[1][1] = -INF;   dp[1][2] = b[1];   dp[1][3] = -INF;   for (int i = 2; i &lt;= n; i++) {     dp[i][0] = a[i] + max(dp[i - 1][2], dp[i - 1][3]);     dp[i][1] = b[i] + max(dp[i - 1][0], dp[i - 1][1]);     dp[i][2] = b[i] + max(dp[i - 1][2], dp[i - 1][3]);     dp[i][3] = c[i] + max(dp[i - 1][0], dp[i - 1][1]);   }   printf("%d\n", max(dp[n][0], dp[n][1]));   return 0; }</pre><p><br/></p>
这道题暂未补解析。