2021年12月青少年C/C++软件编程（四级）等级考试试卷及答案解析_gesp12月c++四级解析

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

目录

1.移动路线

2.移动办公

3.最长公共子上升序列

4.技能树

---

一、编程题(共4题，每题25分，共100分)

1.移动路线

桌子上有一个m行n列的方格矩阵，将每个方格用坐标表示，行坐标从下到上依次递增，列坐标从左至右依次递增，左下角方格的坐标为(1,1)，则右上角方格的坐标为(m,n)。

小明是个调皮的孩子，一天他捉来一只蚂蚁，不小心把蚂蚁的右脚弄伤了，于是蚂蚁只能向上或向右移动。小明把这只蚂蚁放在左下角的方格中，蚂蚁从左下角的方格中移动到右上角的方格中，每步移动一个方格。蚂蚁始终在方格矩阵内移动，请计算出不同的移动路线的数目。

对于1行1列的方格矩阵，蚂蚁原地移动，移动路线数为1；对于1行2列（或2行1列）的方格矩阵，蚂蚁只需一次向右（或向上）移动，移动路线数也为1……对于一个2行3列的方格矩阵，如下图所示：

-------------------
|(2,1)|(2,2)|(2,3)|
-------------------
|(1,1)|(1,2)|(1,3)|
-------------------

蚂蚁共有3种移动路线：
路线1：(1,1) → (1,2) → (1,3) → (2,3)
路线2：(1,1) → (1,2) → (2,2) → (2,3)
路线3：(1,1) → (2,1) → (2,2) → (2,3)

时间限制：1000

内存限制：65536

输入

输入只有一行，包括两个整数m和n（0<m+n<=20），代表方格矩阵的行数和列数，m、n之间用空格隔开

输出

输出只有一行，为不同的移动路线的数目。

样例输入

2 3

样例输出

3

 解析：

对于第一行，只有从左边走过来，只有一条路线

对于第一列，只有从下边走过来，只有一条路线

对于其他位置，都可以从左边走过来，也可以从下边走过来，所以路线数为左边的方案数加上下边的方案数。

详见代码：

#include <bits/stdc++.h>
using namespace std;
int dp[25][25];
int m,n;
int main (){
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if (i==1||j==1){
                dp[i][j]=1;
            }else{
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
    }
    cout<<dp[m][n];
	return 0;
}

2.移动办公

假设你经营着一家公司，公司在北京和南京各有一个办公地点。公司只有你一个人，所以你只能每月选择在一个城市办公。在第i个月，如果你在北京办公，你能获得Pi的营业额，如果你在南京办公，你能获得Ni的营业额。但是，如果你某个月在一个城市办公，下个月在另一个城市办公，你需要支付M的交通费。那么，该怎样规划你的行程（可在任何一个城市开始），才能使得总收入（总营业额减去总交通费）最大？

时间限制：1000

内存限制：65536

输入

输入的第一行有两个整数T（1 <= T <= 100）和M（1 <= M <= 100），T代表总共的月数，M代表交通费。接下来的T行每行包括两个在1到100之间（包括1和100）的的整数，分别表示某个月在北京和在南京办公获得的营业额。

输出

输出只包括一行，这一行只包含一个整数，表示可以获得的最大总收入。

样例输入

4 3

10 9

2 8

9 5

8 2

样例输出

31

解析：动态规划，详见代码： 

#include <bits/stdc++.h>
using namespace std;
//dp[i][0]为第i个月在北京能获得的最大总收入
//dp[i][1]为第i个月在南京能获得的最大总收入
int dp[105][2];
int bj[105];//北京营业额
int nj[105];//南京营业额
int t,m;
int main (){
    cin>>t>>m;
    for(int i=1;i<=t;i++){
        cin>>bj[i]>>nj[i];
    }
    dp[1][0]=bj[1];//从北京开始
    dp[1][1]=nj[1];//从南京开始
    for(int i=2;i<=t;i++){
        //从另一个城市转过来的要减掉交通费，取最大值
        dp[i][0]=bj[i]+max(dp[i-1][0],dp[i-1][1]-m);
        dp[i][1]=nj[i]+max(dp[i-1][1],dp[i-1][0]-m);
    }
    //输出最后一个月的最大值
    cout<<max(dp[t][0],dp[t][1]);
	return 0;
}

3.最长公共子上升序列

给定两个整数序列，写一个程序求它们的最长上升公共子序列。 当以下条件满足的时候，我们将长度为N的序列S1 , S2 , . . . , SN 称为长度为M的序列A1 , A2 , . . . , AM 的上升子序列： 存在 1 <= i1 < i2 < . . . < iN <= M ，使得对所有 1 <= j <=N，均有Sj = Aij，且对于所有的1 <= j < N，均有Sj < Sj+1。

时间限制：10000

内存限制：65536

输入

每个序列用两行表示，第一行是长度M(1 <= M <= 500)，第二行是该序列的M个整数Ai (-231 <= Ai < 231 )

输出

在第一行，输出两个序列的最长上升公共子序列的长度L。在第二行，输出该子序列。如果有不止一个符合条件的子序列，则输出任何一个即可。

样例输入

5

1 4 2 5 -12

4

-12 1 2 4

样例输出

2

1 4

解析：经典动态规划题，详见代码：

#include<bits/stdc++.h>
using namespace std;
#define N 505
int dp[N];//dp[i][j]:x前i个元素与y前j个元素构成的以y[j]为结尾的最长公共上升子序列的长度
int x[N], y[N];
vector<int> seq[N];//seq[j]:当i为某确定值时，x前i个元素与y前j个元素构成的以y[j]为结尾的最长公共上升子序列
int main() {
    int xn, yn;
    cin >> xn;
    for(int i = 1; i <= xn; ++i)
        cin >> x[i];
    cin >> yn;
    for(int i = 1; i <= yn; ++i)
        cin >> y[i];
    for(int i = 1; i <= xn; ++i) {
        int mj = 0;
        for(int j = 1; j <= yn; ++j) {
            if (y[j] < x[i] && dp[j] > dp[mj])
                mj = j;
            if (x[i] == y[j]) {
                dp[j] = dp[mj] + 1;
                seq[j] = seq[mj];
                seq[j].push_back(x[i]);
            }
        }
    }
    int mxj = 1;
    for(int j = 1; j <= yn; j++) {
        if(dp[j] > dp[mxj])
            mxj = j;
    }
    cout << dp[mxj] << endl;
    for(int i = 0; i < seq[mxj].size(); ++i)
        cout << seq[mxj][i] << ' ';
    return 0;
}

4.技能树

设二叉树中每个节点的子节点数为0或2，求有N个节点高度为M的不同的二叉树有多少个
(输出 mod 9901 后的结果)。

时间限制：10000

内存限制：131072

输入

两个空格分开的整数, N和K。

输出

第 1 行: 一个整数，表示可能的技能树的个数除以9901的余数。

样例输入

5 3

样例输出

2

提示

有5个节点，高为3的两个不同的技能树。

约定:n在[3,300]间,m在(1,100)间 

解析：动态规划，详见代码：

#include<bits/stdc++.h>
using namespace std;
const int mod = 9901;
int dp[105][305];//用dp[i][j]表示高度为i，节点数为j的树的种类数，
int sum[305][305];//sum[i][j]，表示节点数为j，高度小于等于i的树的种类数
int main() {
    int n, m;
    cin >> n >> m;
    dp[1][1] = sum[1][1] = 1;
    for (int i = 2; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = 0;
            for (int k = 1; k < j; k++) {
                dp[i][j] = (dp[i][j] + (2 * dp[i - 1][k] * sum[i - 1][j - k - 1] - dp[i - 1][k] * dp[i - 1][j - k - 1]) % mod) % mod;
            }
            sum[i][j] = (sum[i - 1][j] + dp[i][j]) % mod;
        }
    }
    cout << dp[m][n];
    return 0;
}