2021年03月 C/C++(四级)真题解析#中国电子学会#全国青少年软件编程等级考试

在这里插入图片描述

第1题:酒鬼

Santo刚刚与房东打赌赢得了一间在New Clondike 的大客厅。今天,他来到这个大客厅欣赏他的奖品。房东摆出了一行瓶子在酒吧上。瓶子里都装有不同体积的酒。令Santo高兴的是,瓶子中的酒都有不同的味道。房东说道:“你可以喝尽可能多的酒,但是一旦打开酒盖你就必须把它喝完,喝完一瓶后把它放回原处。还有一件最重要的事,你必须从左至右依次喝,并且不能连续超过三瓶,不然会给你带来坏运气。”现在可怜的Santo站在酒吧前努力的想着,他到底应该喝哪几瓶才能使喝的酒最多呢?请帮助他找出他应该喝的酒瓶号,因为思考让他感到不安。
时间限制:2000
内存限制:131072
输入
第一行一个整数N,有N个酒瓶。N<=700接下有N行,第I+1行的数字代表酒瓶I中酒的体积。
输出
一个数字,喝的酒的最大总体积。遵守以上规则,使得三个连续瓶子中至少一个瓶子是满的。
样例输入
6
6
10
13
9
8
1
样例输出
33

要解决这个问题,我们可以使用动态规划来找到喝的酒的最大总体积。

我们可以定义两个数组 dpdpFull,其中 dp[i] 表示从前 i 个酒瓶中喝的酒的最大总体积,而 dpFull[i] 表示从前 i 个酒瓶中喝的酒的最大总体积,并且前 i 个酒瓶中的最后一个瓶子是满的。

根据题目规则,我们可以得到递推关系:

(1)如果第 i 个瓶子不喝,则 dp[i] = dp[i-1]

(2)如果第 i 个瓶子喝,则前一个瓶子不能喝,即 dp[i] = dp[i-2] + volume[i]

(3)如果前两个瓶子都喝,则前三个瓶子不能连续喝,即 dp[i] = dpFull[i-3] + volume[i]

对于 dpFull 数组,有以下递推关系:

(1)如果第 i 个瓶子不喝,则 dpFull[i] = dpFull[i-1]

(2)如果第 i 个瓶子喝,则前一个瓶子不能喝,即 dpFull[i] = dp[i-2] + volume[i]

注意,初始情况下,当只有一个酒瓶时,即 dp[1] = volume[1]dpFull[1] = volume[1]

下面是使用C语言编写的解题代码:

#include <stdio.h>int max(int a, int b) {return (a > b) ? a : b;
}int main() {int N;scanf("%d", &N);int volume[701];int dp[701] = {0};int dpFull[701] = {0};for (int i = 1; i <= N; i++) {scanf("%d", &volume[i]);}dp[1] = volume[1];dpFull[1] = volume[1];for (int i = 2; i <= N; i++) {dp[i] = max(dp[i - 1], max(dp[i - 2] + volume[i], dpFull[i - 3] + volume[i]));dpFull[i] = max(dpFull[i - 1], dp[i - 2] + volume[i]);}printf("%d\n", dp[N]);return 0;
}

在上述代码中,我们首先定义了一个辅助函数 max 来返回两个数中的较大值。

然后,我们定义了一个整数数组 volume,用于存储每个酒瓶的体积。同时,我们定义了两个动态规划数组 dpdpFull,用于计算喝的酒的最大总体积。

接下来,我们使用一个循环来读取输入的酒瓶体积,并存储到 volume 数组中。

然后,我们根据递推关系和初始情况,使用两个循环来计算 dpdpFull 数组的值。

最后,我们输出 dp[N],即喝的酒的最大总体积。

编译并运行上述代码可以解决该问题。你可以使用 C 语言编译器将代码保存为 .c 文件,然后编译并运行该文件来获取结果。

第2题:重启系统

小明帮助管理一个处理数据的计算系统,有N个待处理的任务,需要按照顺序来完成这些任务,即每次所完成任务的编号都要大于前一个完成任务的编号,且单个任务不可以分解完成。计算系统运行着一个奇怪的保护程序,它限制了系统当前所能处理的数据量不能超过上次完成任务所处理的数据量。重启系统可以使它立刻恢复到最高性能(一开始系统拥有最高性能,最高性能大于任何待处理任务的数据量)。小明有一次重启系统的权限(也可以不使用),你能帮他算出最多能完成几个任务吗?
时间限制:1000
内存限制:65536
输入
第一行: N (2 <= N <= 1000) 待处理的任务数 第二行: N个整数,每个任务的数据量
输出
输出只包括一行,这一行只包含一个整数,表示最多能完成的任务数。
样例输入
10
1 5 4 3 2 10 9 8 7 6
样例输出
9
提示
回想一下最长上升子序列问题

要解决这个问题,我们可以使用动态规划来找到最多能完成的任务数。

我们可以定义一个数组 dp,其中 dp[i] 表示以第 i 个任务结尾的最长上升子序列的长度。

根据题目规则,我们可以得到递推关系:

如果第 i 个任务的数据量大于前面任意一个已完成任务的数据量,则 dp[i] = max(dp[j] + 1),其中 j 取值范围为 [0, i-1],且 volume[i] > volume[j]

注意,初始情况下,当只有一个任务时,即 dp[1] = 1

最后,我们遍历整个 dp 数组,找到最大的值,即为最多能完成的任务数。

下面是使用C语言编写的解题代码:

#include <stdio.h>int max(int a, int b) {return (a > b) ? a : b;
}int main() {int N;scanf("%d", &N);int volume[1001];int dp[1001] = {0};for (int i = 1; i <= N; i++) {scanf("%d", &volume[i]);}dp[1] = 1;for (int i = 2; i <= N; i++) {for (int j = 1; j <= i - 1; j++) {if (volume[i] > volume[j]) {dp[i] = max(dp[i], dp[j] + 1);}}}int maxTasks = 0;for (int i = 1; i <= N; i++) {maxTasks = max(maxTasks, dp[i]);}printf("%d\n", maxTasks);return 0;
}

在上述代码中,我们首先定义了一个辅助函数 max 来返回两个数中的较大值。

然后,我们定义了一个整数数组 volume,用于存储每个任务的数据量。

接下来,我们使用一个循环来读取输入的任务数据量,并存储到 volume 数组中。

然后,我们使用两个嵌套循环来计算 dp 数组的值,根据递推关系更新最长上升子序列的长度。

最后,我们遍历整个 dp 数组,找到最大的值,即为最多能完成的任务数。

编译并运行上述代码可以解决该问题。你可以使用 C 语言编译器将代码保存为 .c 文件,然后编译并运行该文件来获取结果。

第3题:鸣人的影分身

在火影忍者的世界里,令敌人捉摸不透是非常关键的。我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。
影分身是由鸣人身体的查克拉能量制造的,使用的查克拉越多,制造出的影分身越强。
针对不同的作战情况,鸣人可以选择制造出各种强度的影分身,有的用来佯攻,有的用来发起致命一击。
那么问题来了,假设鸣人的查克拉能量为M,他影分身的个数为N,那么制造影分身时有多少种(用K表示)不同的分配方法?(影分身可以被分配到0点查克拉能量)
时间限制:1000
内存限制:65536
输入
第一行是测试数据的数目t(0 <= t <= 20)。以下每行均包含二个整数M和N,以空格分开。1 <= M,N <= 10。
输出
对输入的每组数据M和N,用一行输出相应的K。
样例输入
1
7 3
样例输出
8

要解决这个问题,我们可以使用动态规划来计算不同的分配方法。

我们可以定义一个二维数组 dp,其中 dp[i][j] 表示当查克拉能量为 i 时,制造 j 个影分身的不同分配方法数。

根据题目规则,我们可以得到递推关系:

(1)当 j = 0 时,即没有影分身需要制造,那么无论查克拉能量为多少,只有一种分配方法,即不分配任何查克拉给影分身,即 dp[i][0] = 1

(2)当 i = 0 时,即查克拉能量为0,无法制造任何影分身,那么无论需要制造多少个影分身,都没有任何一种分配方法,即 dp[0][j] = 0

(3)对于其他情况,我们可以将第 j 个影分身的查克拉能量从0到 i 进行遍历,并将其分配给第 j 个影分身,然后计算剩余的查克拉能量 i - k 分配给前 j-1 个影分身的不同分配方法数之和,即 dp[i][j] = dp[i][j] + dp[i - k][j - 1],其中 k 取值范围为 [0, i]

最后,我们遍历 dp[M][N],即查克拉能量为 M,制造 N 个影分身的情况下的不同分配方法数。

下面是使用C语言编写的解题代码:

#include <stdio.h>int main() {int t;scanf("%d", &t);while (t--) {int M, N;scanf("%d %d", &M, &N);int dp[11][11] = {0};for (int j = 0; j <= N; j++) {dp[0][j] = 0;}for (int i = 0; i <= M; i++) {dp[i][0] = 1;}for (int i = 1; i <= M; i++) {for (int j = 1; j <= N; j++) {for (int k = 0; k <= i; k++) {dp[i][j] += dp[i - k][j - 1];}}}printf("%d\n", dp[M][N]);}return 0;
}

在上述代码中,我们首先读取测试数据的数目 t

然后,我们使用一个 while 循环来处理每组测试数据。

在每组测试数据中,我们首先读取 MN,即查克拉能量和影分身的个数。

接下来,我们定义一个二维数组 dp,用于计算不同的分配方法数。

然后,我们根据递推关系对 dp 数组进行初始化。

接着,我们使用三个嵌套循环来计算 dp 数组的值,根据递推关系更新不同的分配方法数。

最后,我们输出 dp[M][N],即相应的不同分配方法数。

编译并运行上述代码可以解决该问题。你可以使用 C 语言编译器将代码保存为 .c 文件,然后编译并运行该文件来获取结果。

第4题:宠物小精灵之收服

宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。
一天,小智和皮卡丘来到了小精灵狩猎场,里面有很多珍贵的野生宠物小精灵。小智也想收服其中的一些小精灵。然而,野生的小精灵并不那么容易被收服。对于每一个野生小精灵而言,小智可能需要使用很多个精灵球才能收服它,而在收服过程中,野生小精灵也会对皮卡丘造成一定的伤害(从而减少皮卡丘的体力)。当皮卡丘的体力小于等于0时,小智就必须结束狩猎(因为他需要给皮卡丘疗伤),而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。当小智的精灵球用完时,狩猎也宣告结束。
我们假设小智遇到野生小精灵时有两个选择:收服它,或者离开它。如果小智选择了收服,那么一定会扔出能够收服该小精灵的精灵球,而皮卡丘也一定会受到相应的伤害;如果选择离开它,那么小智不会损失精灵球,皮卡丘也不会损失体力。
小智的目标有两个:主要目标是收服尽可能多的野生小精灵;如果可以收服的小精灵数量一样,小智希望皮卡丘受到的伤害越小(剩余体力越大),因为他们还要继续冒险。
现在已知小智的精灵球数量和皮卡丘的初始体力,已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。请问,小智该如何选择收服哪些小精灵以达到他的目标呢?
时间限制:1000
内存限制:65536
输入
输入数据的第一行包含三个整数:N(0 < N < 1000),M(0 < M < 500),K(0 < K < 100),分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。 之后的K行,每一行代表一个野生小精灵,包括两个整数:收服该小精灵需要的精灵球的数量,以及收服过程中对皮卡丘造成的伤害。
输出
输出为一行,包含两个整数:C,R,分别表示最多收服C个小精灵,以及收服C个小精灵时皮卡丘的剩余体力值最多为R。
样例输入
样例输入1:
10 100 5
7 10
2 40
2 50
1 20
4 20
样例输入2:
10 100 5
8 110
12 10
20 10
5 200
1 110
样例输出
样例输出1:
3 30
样例输出2:
0 100
提示
对于样例输入1:小智选择:(7,10) (2,40) (1,20) 这样小智一共收服了3个小精灵,皮卡丘受到了70点伤害,剩余100-70=30点体力。所以输出3 30 对于样例输入2:小智一个小精灵都没法收服,皮卡丘也不会收到任何伤害,所以输出0 100
运行测试
控制台:清理控制台

解题思路如下:

(1)首先,我们需要使用动态规划来解决这个问题。我们定义一个二维数组 dp[N+1][M+1],其中 dp[i][j] 表示使用前 i 个精灵球,对于剩余体力为 j 的情况下,可以收服的最多小精灵数量。

(2)初始化 dp 数组:对于 dp[0][j](即使用 0 个精灵球),无论剩余体力是多少,都无法收服小精灵,所以初始化为 0。对于 dp[i][0](即剩余体力为 0),无论使用多少个精灵球,都无法继续冒险,所以初始化为 0。

(3)根据递推关系更新 dp 数组的值:对于每一个小精灵,我们有两种选择:收服它或者离开它。如果选择收服它,我们需要考虑两个因素:使用精灵球的数量和对皮卡丘造成的伤害。我们遍历所有可能的精灵球数和伤害,更新 dp[i][j] 的值为 max(dp[i-1][j], dp[i-1][j-damage] + balls),其中 ballsdamage 分别表示第 i 个小精灵需要的精灵球数和对皮卡丘造成的伤害。

(4)最后,我们遍历整个 dp 数组,找到收服小精灵数量最大的值 max_captured,以及对应的剩余体力最大值 max_remain_hp

(5)输出 max_capturedmax_remain_hp

以下是根据题目要求的 C 语言解题代码:

#include <stdio.h>int max(int a, int b) {return (a > b) ? a : b;
}int main() {int N, M, K;scanf("%d %d %d", &N, &M, &K);int dp[N + 1][M + 1];int balls[K], damage[K];for (int i = 0; i < K; i++) {scanf("%d %d", &balls[i], &damage[i]);}for (int i = 0; i <= N; i++) {for (int j = 0; j <= M; j++) {if (i == 0 || j == 0) {dp[i][j] = 0;} else {dp[i][j] = dp[i - 1][j];if (j >= damage[i - 1]) {dp[i][j] = max(dp[i][j], dp[i - 1][j - damage[i - 1]] + balls[i - 1]);}}}}int max_captured = 0;int max_remain_hp = M;for (int i = 0; i <= N; i++) {for (int j = 0; j <= M; j++) {if (dp[i][j] > max_captured) {max_captured = dp[i][j];max_remain_hp = M - j;}}}printf("%d %d\n", max_captured, max_remain_hp);return 0;
}

这里我们使用了一个 max 函数来返回两个数中的较大值。

然后,我们定义了一个二维数组 dp 来存储中间结果,并且定义了两个数组 ballsdamage 来存储每个野生小精灵的精灵球数和伤害值。

接下来,我们使用两个嵌套循环来计算 dp 数组的值,根据递推关系更新 dp[i][j] 的值。

最后,我们遍历整个 dp 数组,找出最大值以及对应的索引,即可以收服的最大数量的小精灵和皮卡丘剩余体力的最大值。然后输出这两个值。

运行以上代码,即可得到结果。你可以将代码保存为 .c 文件,然后编译运行该文件来获取结果。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/102911.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

机器学习深度学习——针对序列级和词元级应用微调BERT

&#x1f468;‍&#x1f393;作者简介&#xff1a;一位即将上大四&#xff0c;正专攻机器学习的保研er &#x1f30c;上期文章&#xff1a;机器学习&&深度学习——NLP实战&#xff08;自然语言推断——注意力机制实现&#xff09; &#x1f4da;订阅专栏&#xff1a;机…

游戏开发服务器选型的横向对比

来源一个某乎的作者&#xff0c;貌似来自台湾 上篇介绍了go版本的游戏服务器&#xff0c;这篇介绍下其它语言版本&#xff1a; SkynetkbengineNoahGameFramePomeloPinusET使用的语言C/LuaCCNodejsTypeScriptC#概述云风前辈开源的框架mmo框架server一个快速的、可扩展的、分布…

win11出现安全中心空白和IT管理员已限制对此应用的某些区域的访问

问题 windows安全中心服务被禁用 winr 输入services.msc 找到windows安全中心服务查看是否被禁用&#xff0c;改为启动&#xff0c;不可以改动看第三条 打开设置&#xff0c;找到应用—windows安全中心–终止–修复–重置 重启如果还是不行看第四条 家庭版系统需要打开gped…

我是怎么从0到1搭建性能门禁系统的

背景 页面的性能对于用户的体验起着至关重要的作用&#xff0c;根据Mobify 研究发现&#xff0c;首页加载时间每减少100 毫秒&#xff0c;用户留存率就会增加1.11%。所以做好页面的性能优化&#xff0c;对于网站来说是一个非常重要的步骤。 在解决问题之前需要度量问题&#x…

期权分仓开户资金是否安全?具体保障措施有哪些?

网上关于期权分仓系统的真假一直都没有定论&#xff0c;两方人的争论也让很多没有接触过期权分仓系统的人摸不着头脑&#xff0c;那么期权分仓靠谱吗&#xff1f;资金在里面安全吗&#xff1f;下文为大家科普期权分仓开户资金是否安全?具体保障措施有哪些&#xff1f; 一、期权…

arm:day9

1。思维导图 2..I2C实验&#xff0c;检测温度和湿度 iic.h #ifndef __IIC_H__ #define __IIC_H__ #include "stm32mp1xx_gpio.h" #include "stm32mp1xx_rcc.h" #include "gpio.h" /* 通过程序模拟实现I2C总线的时序和协议* GPIOF ---> AHB4…

指针(初阶)

1. 指针是什么&#xff1f; 指针是什么&#xff1f; 指针理解的2个要点&#xff1a; 1. 指针是内存中一个最小单元的编号&#xff0c;也就是地址 2. 平时口语中说的指针&#xff0c;通常指的是指针变量&#xff0c;是用来存放内存地址的变量 总结&#xff1a;指针就是地址&…

K8s中的Namespace是什么?

如何理解Namespace默认的Namespace使用Namespace的好处创建和使用Namespace使用命令行创建使用YAML文件创建Namespace 用例切换Namespace删除Namespace 感谢 &#x1f496; hello大家好&#x1f60a; 由于能够无缝管理和扩展工作负载&#xff0c;Kubernetes &#xff08;简称K8…

【图论】拓扑排序

一.定义 拓扑排序是一种对有向无环图&#xff08;DAG&#xff09;进行排序的算法&#xff0c;使得图中的每个顶点在排序中都位于其依赖的顶点之后。它通常用于表示一些任务之间的依赖关系&#xff0c;例如在一个项目中&#xff0c;某些任务必须在其他任务之前完成。 拓扑排序的…

Flutter对象状态动态监听Watcher

场景&#xff1a;当一个表单需要在表单全部或者特定项赋值后才会让提交按钮可点击。 1.普通实现方式&#xff1a; ///场景&#xff1a;检查[test11][test12][test13]均不为空时做一些事情&#xff0c;例如提交按钮变成可点击String? test11;String? test12;int? test13;///当…

rust库学习-env_logger(actix-web添加彩色日志、rust添加彩色日志 )

文章目录 介绍actix-web启用彩色日志crate地址&json格式日志 我们在进行rust的web开发时&#xff0c;如果不指定日志&#xff0c;就不会有输出&#xff0c;非常不友好 这里我们使用env_logger进行日志打印 介绍 env_logger 需要配合 log 库使用, env_logger 是 Rust 社区…

Docker基本部署和相关操作

1.安装docker服务&#xff0c;配置镜像加速器 1、yum安装并且添加源信息 yum install yum-utils device-mapper-persistent-data lvm2 -y yum-config-manager --add-repo https://mirrors.tuna.tsinghua.edu.cn/docker-ce/linux/centos/docker-ce.repo2、修改一些配置信息 sed…

视频监控平台EasyCVR视频汇聚平台档案库房图书馆等可视化管理平台应用场景全面解析

档案是一种特殊的记录留存文献&#xff0c;具有珍贵的精神财富价值。它们是人类活动的真实见证&#xff0c;是辉煌时刻的历史记录&#xff0c;在社会发展和经济建设中发挥着至关重要的作用。 随着市场经济的不断发展和人类文明的飞速推进&#xff0c;档案的价值和作用变得越来…

C#实现简单TCP服务器和客户端网络编程

在C#中进行网络编程涉及许多类和命名空间&#xff0c;用于创建和管理网络连接、传输数据等。下面是一些主要涉及的类和命名空间&#xff1a; System.Net 命名空间&#xff1a;这个命名空间提供了大部分网络编程所需的类&#xff0c;包括&#xff1a; IPAddress&#xff1a;用于…

数据结构(6)

2-3查找树 2-结点&#xff1a;含有一个键(及其对应的值)和两条链&#xff0c;左链接指向2-3树中的键都小于该结点&#xff0c;右链接指向的2-3树中的键都大于该结点。 3-结点&#xff1a;含有两个键(及其对应的值)和三条链&#xff0c;左链接指向的2-3树中的键都小于该结点&a…

什么是JVM ?

目录 一、JVM 简介 1.1 JVM 发展史 1.Sun Classic VM 2.Exact VM 3.HotSpot VM 4.JRockit 5.J9 JVM 6.Taobao JVM&#xff08;国产研发&#xff09; 1.2 JVM 和《Java虚拟机规范》 二、 JVM 运行流程 JVM 执行流程 三、JVM 运行时数据区 3.1 堆&#xff08;线程共享…

【TypeScript】声明文件

在 TypeScript 中&#xff0c;声明文件&#xff08;Declaration Files&#xff09;用于描述已有 JavaScript 代码库的类型信息&#xff0c;以便在 TypeScript 项目中使用这些代码库时获得类型支持。 当你在 TypeScript 项目中引用外部 JavaScript 模块或库时&#xff0c;可能会…

【开发】tips:视频汇聚/视频云存储/视频监控管理平台EasyCVR如何提升网络稳定

安防视频监控/视频集中存储/云存储/磁盘阵列EasyCVR平台可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及支持厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等。平台既具备传统安…

字节跳动 从需求到上线全流程 软件工程流程 需求评估 MVP

走进后端开发流程 整个课程会带大家先从理论出发&#xff0c;思考为什么有流程 大家以后工作的团队可能不一样&#xff0c;那么不同的团队也会有不同的流程&#xff0c;这背后的逻辑是什么 然后会带大家按照走一遍从需求到上线的全流程&#xff0c;告诉大家在流程的每个阶段&am…

iOS 分别对一张图的局部进行磨砂,拼接起来不能贴合

效果图 需求&#xff0c;由于视图层级的原因&#xff0c;需要对图片分开进行磨砂&#xff0c; 然后组合在一起 如图&#xff0c;上下两部分&#xff0c;上下两个UIImageVIew大小相同&#xff0c;都是和图片同样的大小&#xff0c;只是上面的UIimageVIew 只展示上半部份 &#…