2022年12月青少年C/C++软件编程（四级）等级考试试卷及答案解析_gesp c++ 四级真题含答案

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

目录

1.开餐馆

2.糖果

3.鸡蛋的硬度

4.山区建小学

---

1.开餐馆

北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n 个地点排列在同一条直线上。我们用一个整数序列m1, m2, ... mn 来表示他们的相对位置。由于地段关系,开餐馆的利润会有所不同。我们用pi 表示在mi 处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于k。请你帮助小明选择一个总利润最大的方案。

时间限制：1000

内存限制：65536

输入

标准的输入包含若干组测试数据。输入第一行是整数T (1 <= T <= 1000) ，表明有T组测试数据。紧接着有T组连续的测试。每组测试数据有3行, 第1行:地点总数 n (n < 100), 距离限制 k (k > 0 && k < 1000). 第2行:n 个地点的位置m1 , m2, ... mn ( 1000000 > mi > 0 且为整数,升序排列) 第3行:n 个地点的餐馆利润p1 , p2, ... pn ( 1000 > pi > 0 且为整数)

输出

对于每组测试数据可能的最大利润

样例输入

2

3 11

1 2 15

10 2 30

3 16

1 2 15

10 2 30

样例输出

40

30

解析：定义dp[i]为 在第i个位置开餐馆最多的盈利。

针对每个位置，找到它前面k距离之外总盈利最大的餐馆，加上当前位置餐馆的盈利

时间复杂度O(TN^2),详见代码：

#include <bits/stdc++.h>
using namespace std;
int dp[105];//dp[i]表示在第i个位置开餐馆最多的盈利数
int m[105];//距离
int p[105];//盈利
int t,n,k;
int ans;
int main() {
    scanf("%d",&t);
    while (t--){//循环t组数据
        scanf("%d %d",&n,&k);
        for (int i=1;i<=n;i++){
            scanf("%d",&m[i]);
        }
        for (int i=1;i<=n;i++){
            scanf("%d",&p[i]);
        }
        memset(dp,0,sizeof(dp));//清空
        for (int i=1;i<=n;i++){//针对每个位置
            dp[i]=0;
            int t=0;
            //找到前边k距离之外能够获得盈利的最大值
            for (int j=i-1;j>=1;j--){
                if (m[i]-m[j]>k){
                    t=max(t,dp[j]);
                }
            }
            dp[i]=p[i]+t;//加上当前位置的盈利
        }
        ans=0;
        //取所有位置开店盈利的最大值，即为答案
        for (int i=1;i<=n;i++){
            ans=max(ans,dp[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

2.糖果

由于在维护世界和平的事务中做出巨大贡献，Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。在这一天，Dzx可以从糖果公司的N件产品中任意选择若干件带回家享用。糖果公司的N件产品每件都包含数量不同的糖果。Dzx希望他选择的产品包含的糖果总数是K的整数倍，这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。当然，在满足这一条件的基础上，糖果总数越多越好。Dzx最多能带走多少糖果呢？ 注意：Dzx只能将糖果公司的产品整件带走。

时间限制：7000

内存限制：65536

输入

第一行包含两个整数N(1<=N<=100)和K(1<=K<=100) 以下N行每行1个整数，表示糖果公司该件产品中包含的糖果数目，不超过1000000

输出

符合要求的最多能达到的糖果总数，如果不能达到K的倍数这一要求，输出0

样例输入

5 7

1

2

3

4

5

样例输出

14

提示

Dzx的选择是2+3+4+5=14，这样糖果总数是7的倍数，并且是总数最多的选择。

 解析：

定义dp[i][j]表示截止第i个产品，余数是j的最大数量，若为0，表示不存在

从第一个产品开始，

对于上一产品余数为0的情况，直接加当前产品数量，求余，放入指定位置。

对于上一产品其他余数，只要存在（数量不为零），加上当前产品数量，求余，放入指定位置。

对于当前产品所有余数情况，如果不如上一产品的情况，就用上一产品的数量。

最后求出所有产品中余数为零的情况的最大值，即为答案。

详见代码：

#include <bits/stdc++.h>
using namespace std;
int a[105];//糖果数量
int dp[105][105];//dp[i][j]表示截止第i个产品，余数是j的最大数量
int n,k;
int ans=0;
 
int main() {
    cin>>n>>k;
    for (int i=1;i<=n;i++){
            cin>>a[i];
    }
    for (int i=1;i<=n;i++){//对于第i个产品
        //针对上个产品余数为零的情况
        dp[i][a[i]%k]=dp[i-1][0]+a[i];
        for (int j=0;j<k;j++){//对于上一产品所有余数的情况
            //只要有数量，加上当前产品，求余数，放到相应位置
            if (dp[i-1][j]!=0)
                dp[i][(j+a[i])%k]=dp[i-1][j]+a[i];
        }
        //对于加了不如不加的情况，不加
        for (int j=0;j<k;j++){
            dp[i][j]=max(dp[i][j],dp[i-1][j]);
        }
    }
    //找到余数为零的最大值
    for (int i=1;i<=n;i++){
        ans=max(ans,dp[i][0]);
    }
    cout<<ans;
    return 0;
}

3.鸡蛋的硬度

最近XX公司举办了一个奇怪的比赛：鸡蛋硬度之王争霸赛。参赛者是来自世 界各地的母鸡，比赛的内容是看谁下的蛋最硬，更奇怪的是XX公司并不使用什么精密仪器来测量蛋的硬度，他们采用了一种最老土的办法--从高度扔鸡蛋--来 测试鸡蛋的硬度，如果一次母鸡下的蛋从高楼的第a层摔下来没摔破，但是从a+1层摔下来时摔破了，那么就说这只母鸡的鸡蛋的硬度是a。你当然可以找出各种 理由说明这种方法不科学，比如同一只母鸡下的蛋硬度可能不一样等等，但是这不影响XX公司的争霸赛，因为他们只是为了吸引大家的眼球，一个个鸡蛋从100 层的高楼上掉下来的时候，这情景还是能吸引很多人驻足观看的，当然，XX公司也绝不会忘记在高楼上挂一条幅，写上“XX公司”的字样--这比赛不过是XX 公司的一个另类广告而已。
勤于思考的小A总是能从一件事情中发现一个数学问题，这件事也不例外。“假如有很多同样硬度的鸡蛋，那么我可以用二分的办法用最少的次数测出鸡蛋 的硬度”，小A对自己的这个结论感到很满意，不过很快麻烦来了，“但是，假如我的鸡蛋不够用呢，比如我只有1个鸡蛋，那么我就不得不从第1层楼开始一层一 层的扔，最坏情况下我要扔100次。如果有2个鸡蛋，那么就从2层楼开始的地方扔……等等，不对，好像应该从1/3的地方开始扔才对，嗯，好像也不一定 啊……3个鸡蛋怎么办，4个，5个，更多呢……”，和往常一样，小A又陷入了一个思维僵局，与其说他是勤于思考，不如说他是喜欢自找麻烦。
好吧，既然麻烦来了，就得有人去解决，小A的麻烦就靠你来解决了：）

时间限制：1000

内存限制：65536

输入

输入包括多组数据，每组数据一行，包含两个正整数n和m(1<=n<=100,1<=m<=10)，其中n表示楼的高度，m表示你现在拥有的鸡蛋个数，这些鸡蛋硬度相同（即它们从同样高的地方掉下来要么都摔碎要么都不碎），并且小于等于n。你可以假定硬度为x的鸡蛋从高度小于等于x的地方摔无论如何都不会碎（没摔碎的鸡蛋可以继续使用），而只要从比x高的地方扔必然会碎。 对每组输入数据，你可以假定鸡蛋的硬度在0至n之间，即在n+1层扔鸡蛋一定会碎。

输出

对于每一组输入，输出一个整数，表示使用最优策略在最坏情况下所需要的扔鸡蛋次数。

样例输入

100 1

100 2

样例输出

100

14

提示

最优策略指在最坏情况下所需要的扔鸡蛋次数最少的策略。 如果只有一个鸡蛋，你只能从第一层开始扔，在最坏的情况下，鸡蛋的硬度是100，所以需要扔100次。如果采用其他策略，你可能无法测出鸡蛋的硬度(比如你第一次在第二层的地方扔,结果碎了,这时你不能确定硬度是0还是1)，即在最坏情况下你需要扔无限次，所以第一组数据的答案是100。

解析：

定义dp[i][j]表示i层楼j个鸡蛋最优策略在最坏情况下的扔鸡蛋次数

对于第j个鸡蛋，枚举第j个鸡蛋从第k（1到i）层扔，找到最优策略的最大值；

碎了的情况和不碎的情况需要扔鸡蛋的最大值
碎了，楼层少一层（k-1），鸡蛋少一个（j-1）即dp[k-1][j-1]
没碎，楼层k往下不用测了，变成（i-k），鸡蛋不变（j）即dp[i-k][j]
最后加1，是加上本次
在这些最大值中取最小值，为最优策略

详见代码：

#include<bits/stdc++.h>
using namespace std;
int dp[105][105];//dp[i][j]表示i层楼j个鸡蛋最优策略在最坏情况下的扔鸡蛋次数
int n,m;//n层楼，m个鸡蛋
int main() {
    n=100;
    m=10;
    //对于1层楼，最多一次
    for (int i=1;i<=m;i++){
        dp[1][i]=1;
    }
    //对于一个鸡蛋的情况，几层楼就几次
    for (int i=1;i<=n;i++){
        dp[i][1]=i;
    }
    for (int i=2;i<=n;i++){//从第二层楼开始
        for (int j=2;j<=m;j++){//每层从第二个鸡蛋开始
            dp[i][j]=1e9;//默认最大值
            for (int k=1;k<i;k++){//枚举第j个鸡蛋从第k（1到i）层扔
                //碎了的情况和不碎的情况需要扔鸡蛋的最大值
                //碎了，楼层少一层（k-1），鸡蛋少一个（j-1）即dp[k-1][j-1]
                //没碎，楼层k往下不用测了，变成（i-k），鸡蛋不变（j）即dp[i-k][j]
                //最后加1，是加上本次
                //在这些最大值中取最小值，为最优策略
                dp[i][j]=min(dp[i][j],max(dp[k-1][j-1],dp[i-k][j])+1);
            }
        }
    }
    //输出结果
    while (scanf("%d %d",&n,&m)!=EOF){
        printf("%d\n",dp[n][m]);
    }
    return 0;
}

4.山区建小学

政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为di（为正整数），其中，0 < i < m。为了提高山区的文化素质，政府又决定从m个村中选择n个村建小学（设 0 < n < = m < 500 ）。请根据给定的m、n以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小，计算最小值。

时间限制：24000

内存限制：65536

输入

第1行为m和n，其间用空格间隔 第2行为(m-1) 个整数，依次表示从一端到另一端的相邻村庄的距离，整数之间以空格间隔。 例如 10 3 2 4 6 5 2 4 3 1 3 表示在10个村庄建3所学校。第1个村庄与第2个村庄距离为2，第2个村庄与第3个村庄距离为4，第3个村庄与第4个村庄距离为6，...，第9个村庄到第10个村庄的距离为3。

输出

各村庄到最近学校的距离之和的最小值。

样例输入

10 2

3 1 3 1 1 1 1 1 3

样例输出

18

 解析：动态规划

首先要明确一点，如果给x个村子，中间建一所小学，应该怎么选址，使路程和最短；

答案是选中间的村子，如果奇数个村子，选中间的，偶数个选中间的两个都一样；

证明如下：

对于5个村子的情况，如果我们把小学建在3号村，总路程长度为L，若我们把小学挪到2号村子，左边的1,2号村子减少了路程L2，右边的3,4,5号村子路程增加了L2，总路程增加了L2，同理，挪到4号村子，总路程增加L3，对于偶数个村子同理。 

我们可以提前计算出一所小学覆盖从i号到j号村，各村到小学的路程总和，即c[i][j]。

对于i个村子j个小学的情况，我们可以枚举最后一个小学覆盖的村子，找出不同情况下总路程和的最小值。

边界条件，对于一所小学，从1到m个村子的情况总路程和的最小值为c[1][i]。

详见代码：

#include<bits/stdc++.h>
using namespace std;
int dp[505][505];//dp[i][j]表示i个村子建j个小学最小的距离总和
int c[505][505];//c[i][j]表示从第i个村子到第j个村子之间建一个小学，这些村子到学校的路程最小总和
int n,m;//n个小学，m个村子
int a[505];//村子之间的距离
int main() {
    cin>>m>>n;
    for(int i=2;i<=m;i++){
        cin>>a[i];
        a[i]+=a[i-1];//求前缀和，即第i个村子到第一个村子的距离
    }
    for (int i=1;i<=m;i++){//计算c[i][j]
        for(int j=i+1;j<=m;j++){
            int mid=(i+j)/2;//建小学的村子
            for(int k=i;k<=j;k++){//求距离和
                c[i][j]+=abs(a[k]-a[mid]);
            }
        }
    }
    //只建一个小学的情况
    for(int i=1;i<=m;i++){
        dp[i][1]=c[1][i];
    }
 
    for(int i=1;i<=m;i++){
        for(int j=2;j<=n;j++){
            if(j>=i) continue;
            dp[i][j]=1e9;
            //枚举j-1个小学覆盖的村子，由第j个小学覆盖剩下的村子
            for(int k=j-1;k<i;k++){
                //找出不同覆盖情况下，最小的路程和
                dp[i][j]=min(dp[i][j],dp[k][j-1]+c[k+1][i]);
            }
 
        }
    }
    cout<<dp[m][n];
    return 0;
}