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

在这里插入图片描述

第1题:拦截导弹

某国为了防御敌国的导弹袭击, 发展出一种导弹拦截系统。 但是这种导弹拦截系统有一个缺陷: 虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。 某天, 雷达捕捉到敌国的导弹来袭。 由于该系统还在试用阶段, 所以只有一套系统, 因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度(雷达给出的高度数据是不大于 30000 的正整数) , 计算这套系统最多能拦截多少导弹。
时间限制: 1000
内存限制: 65536
输入
第一行是一个整数 N(不超过 15) , 表示导弹数。 第二行包含 N 个整数, 为导弹依次飞来的高度(雷达给出的高度数据是不大于 30000的正整数) 。
输出
一个整数, 表示最多能拦截的导弹数。
样例输入
8
389 207 155 300 299 170 158 65
样例输出
6

要解决拦截导弹的问题,可以使用动态规划的方法。

以下是使用C语言实现的代码:

#include <stdio.h>#define MAX_MISSILES 15int max(int a, int b) {return (a > b) ? a : b;
}int missileInterception(int missiles[], int n) {int dp[MAX_MISSILES] = {0};int maxInterceptions = 0;for (int i = 0; i < n; i++) {dp[i] = 1;for (int j = 0; j < i; j++) {if (missiles[i] <= missiles[j]) {dp[i] = max(dp[i], dp[j] + 1);}}maxInterceptions = max(maxInterceptions, dp[i]);}return maxInterceptions;
}int main() {int n;scanf("%d", &n);int missiles[MAX_MISSILES];for (int i = 0; i < n; i++) {scanf("%d", &missiles[i]);}int maxInterceptions = missileInterception(missiles, n);printf("%d\n", maxInterceptions);return 0;
}

该代码使用一个一维数组dp来保存状态,其中dp[i]表示以第i个导弹为结尾的最大拦截导弹数。

首先,初始化dp数组的所有元素为1,表示每个导弹都可以单独拦截。然后,遍历导弹数组,对于每个导弹missiles[i],在之前的导弹中查找高度小于等于当前导弹的导弹missiles[j],如果找到,则更新dp[i]为dp[j]+1,表示以导弹missiles[i]结尾的最大拦截导弹数。最后,找到dp数组中的最大值即为所求的最多能拦截的导弹数。

第2题:神奇的数列

一个正整数数列, 可以将它切割成若干个数据段, 每个数据段由值相同的相邻元素构成。 该数列的神奇之处在于, 每次切除一个数据段后,该数据段前后的元素自动连接在一起成为邻居。 例如从数列“2 8 9 77 6 9 4” 中切除数据段“7 7 ” 后, 余下的元素会构成数列“2 8 9 6 94”
请问若要将该数列切割成若干个数据段, 则至少会切出来几个数据段?
样例: 按下列顺序切割数列“2 8 9 7 7 6 9 4” , 只要切割成 6 段
切割出“7 7” , 余下 “2 8 9 6 9 4”
切割出 “6” , 余下 “2 8 9 9 4”
切割出 “9 9” , 余下 “2 8 4”
切割出 “2” , 余下 “8 4”
切割出 “8” , 余下 “4”
时间限制: 1000
内存限制: 65536
输入
第一行是一个整数, 示共有多少组测试数据。 每组测试数据的输入包括两行: 第一行是整数 N, N<=200,表示数列的长度, 第二行是 N 个正整数。
输出
每个测试案例的输出占一行, 是一个整数。 格式是: Case n: x n 是测试数据组编号, x 是答案
样例输入
2
8
2 8 9 7 7 6 9 4
16
2 8 9 7 7 6 9 4 4 2 8 4 2 7 6 9
样例输出
Case 1: 6
Case 2: 11

要解决神奇的数列问题,可以使用贪心算法。

以下是使用C语言实现的代码:

#include <stdio.h>#define MAX_LENGTH 200int min(int a, int b) {return (a < b) ? a : b;
}int countSegments(int sequence[], int n) {int segments = 1;for (int i = 1; i < n; i++) {if (sequence[i] != sequence[i - 1]) {segments++;}}return segments;
}int main() {int t;scanf("%d", &t);for (int i = 1; i <= t; i++) {int n;scanf("%d", &n);int sequence[MAX_LENGTH];for (int j = 0; j < n; j++) {scanf("%d", &sequence[j]);}int segments = countSegments(sequence, n);printf("Case %d: %d\n", i, segments);}return 0;
}

该代码使用一个循环遍历数列,对于每个数列元素sequence[i],如果它与前一个元素sequence[i-1]不相等,则将段数segments加1。最后,segments的值即为所求的切割数据段的数量。

第3题:硬币

宇航员 Bob 有一天来到火星上, 他有收集硬币的习惯。 于是他将火星上所有面值的硬币都收集起来了, 一共有 n 种, 每种只有一个: 面值分别为 a1,a2… an。 Bob 在机场看到了一个特别喜欢的礼物, 想买来送给朋友 Alice, 这个礼物的价格是 X 元。 Bob 很想知道为了买这个礼物他的哪些硬币是必须被使用的, 即 Bob 必须放弃收集好的哪些硬币种类。 飞机场不提供找零, 只接受恰好 X 元。
时间限制: 1000
内存限制: 262144
输入
第一行包含两个正整数 n 和 x。 (1 <= n <= 200, 1 <= x <= 10000) 第二行从小到大为 n 个正整数 a1, a2, a3 … an (1 <= ai <= 10000)
输出
第一行是一个整数, 即有多少种硬币是必须被使用的。 第二行是这些必须使用的硬币的面值(从小到大排列) 。
样例输入
5 18
1 2 3 5 10
样例输出
2
5 10
提示
输入数据将保证给定面值的硬币中至少有一种组合能恰好能够支付 X元。 如果不存在必须被使用的硬币, 则第一行输出 0, 第二行输出空行。

要解决硬币问题,可以使用动态规划的方法。

以下是使用C语言实现的代码:

#include <stdio.h>
#include <stdbool.h>#define MAX_COINS 200
#define MAX_AMOUNT 10000bool dp[MAX_AMOUNT + 1] = {false};void findCoins(int coins[], int n, int amount) {dp[0] = true;for (int i = 0; i < n; i++) {for (int j = amount; j >= coins[i]; j--) {if (dp[j - coins[i]]) {dp[j] = true;}}}
}int main() {int n, amount;scanf("%d %d", &n, &amount);int coins[MAX_COINS];for (int i = 0; i < n; i++) {scanf("%d", &coins[i]);}findCoins(coins, n, amount);int count = 0;for (int i = 1; i <= amount; i++) {if (dp[i]) {count++;}}printf("%d\n", count);for (int i = 1; i <= amount; i++) {if (dp[i]) {printf("%d ", i);}}printf("\n");return 0;
}

该代码使用一个布尔数组dp来保存状态,其中dp[i]表示是否存在一种硬币组合,可以凑出金额i。

首先,将dp[0]设置为true,表示金额为0时不需要使用任何硬币。然后,遍历硬币数组coins,对于每个硬币coins[i],从amount向前遍历到coins[i],如果存在一种硬币组合可以凑出金额j-coins[i],则说明存在一种硬币组合可以凑出金额j,将dp[j]设置为true。

最后,统计dp数组中为true的元素个数,即为必须被使用的硬币种类的数量。并输出这些必须使用的硬币面值。

第4题:公共子序列

我们称序列 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

要解决最大公共子序列问题,可以使用动态规划的方法。

以下是使用C语言实现的代码:

#include <stdio.h>
#include <string.h>#define MAX_LENGTH 200int max(int a, int b) {return (a > b) ? a : b;
}int longestCommonSubsequence(char X[], char Y[], int m, int n) {int dp[MAX_LENGTH + 1][MAX_LENGTH + 1];for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {if (i == 0 || j == 0) {dp[i][j] = 0;} else if (X[i - 1] == Y[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[m][n];
}int main() {char X[MAX_LENGTH + 1];char Y[MAX_LENGTH + 1];while (scanf("%s %s", X, Y) != EOF) {int m = strlen(X);int n = strlen(Y);int length = longestCommonSubsequence(X, Y, m, n);printf("%d\n", length);}return 0;
}

该代码使用一个二维数组dp来保存状态,其中dp[i][j]表示序列X的前i个字符和序列Y的前j个字符的最大公共子序列的长度。

首先,将dp[i][0]和dp[0][j]都设置为0,表示当一个序列的长度为0时,最大公共子序列的长度为0。

然后,从1到m和1到n的循环遍历,如果X[i-1]等于Y[j-1],则说明X的第i个字符和Y的第j个字符相同,将dp[i][j]设置为dp[i-1][j-1]的值加1,表示当前字符可以加入最大公共子序列。

如果X[i-1]不等于Y[j-1],则说明X的第i个字符和Y的第j个字符不相同,需要在X的前i-1个字符和Y的前j个字符的最大公共子序列和X的前i个字符和Y的前j-1个字符的最大公共子序列之间取最大值,即dp[i-1][j]和dp[i][j-1]的最大值。

最后,dp[m][n]即为X和Y的最大公共子序列的长度。

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

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

相关文章

yolov8热力图可视化

安装pytorch_grad_cam pip install grad-cam自动化生成不同层的bash脚本 # 循环10次&#xff0c;将i的值从0到9 for i in $(seq 0 13) doecho "Running iteration $i";python yolov8_heatmap.py $i; done热力图生成python代码 import warnings warnings.filterwarn…

同源策略以及SpringBoot的常见跨域配置

先说明一个坑。在跨域的情况下&#xff0c;浏览器针对复杂请求&#xff0c;会发起预检OPTIONS请求。如果服务端对OPTIONS进行拦截&#xff0c;并返回非200的http状态码。浏览器一律提示为cors error。 一、了解跨域 1.1 同源策略 浏览器的同源策略&#xff08;Same-Origin Po…

Django学习笔记-AcApp端授权AcWing一键登录

笔记内容转载自 AcWing 的 Django 框架课讲义&#xff0c;课程链接&#xff1a;AcWing Django 框架课。 AcApp 端使用 AcWing 一键授权登录的流程与之前网页端的流程一样&#xff0c;只有申请授权码这一步有一点细微的差别&#xff1a; 我们在打开 AcApp 应用之后会自动向 AcW…

05.sqlite3学习——DML(数据管理:插入、更新、删除)

目录 DML&#xff08;数据管理&#xff1a;插入、更新、删除&#xff09; 插入 更新 删除整个表 语法 实例 DML&#xff08;数据管理&#xff1a;插入、更新、删除&#xff09; 数据操纵&#xff08;DML&#xff09;&#xff1a;用于增、删、改数据 作用&#xff1a;负…

Java设计模式-职责链模式

1 概述 在现实生活中&#xff0c;常常会出现这样的事例&#xff1a;一个请求有多个对象可以处理&#xff0c;但每个对象的处理条件或权限不同。例如&#xff0c;公司员工请假&#xff0c;可批假的领导有部门负责人、副总经理、总经理等&#xff0c;但每个领导能批准的天数不同…

Mac OS 13.4.1 搜狗输入法导致的卡顿问题

一、Mac OS 系统版本 搜狗输入法已经更新到最新 二、解决方案 解决方案一 在我的电脑上面需要关闭 VSCode 和 Chrmoe 以后&#xff0c;搜狗输入法回复正常。 解决方案二 强制重启一下搜狗输入法。 可以用 unix 定时任务去隔 2个小时自动 kill 掉一次进程 # kill 掉 mac …

【SpringBoot】第一篇:redis使用

背景&#xff1a; 本文是教初学者如何正确使用和接入redis。 一、引入依赖 <!--redis--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId></dependency><depen…

MyBatis快速入门以及环境搭建和CRUD的实现

目录 前言 一、MyBatis简介 1.MyBatis是什么 2.MyBatis的特点 3.mybatis的作用 4.MyBatis的应用场景 5.MyBatis优缺点 二、相关概念 1.ORM概述 2.常见的ORM框架 3.什么是持久层框架 三、MyBatis的工作原理 1.框架交互 2.工作原理 ​编辑 四、MyBatis环境搭建 1…

多次跑网络流(用于构造类)+霍尔定理证明可行:AGC317G

https://atcoder.jp/contests/abc317/tasks/abc317_g 一个很显然的思路&#xff0c;就是行向颜色连边&#xff0c;但约束条件展现出多个维度&#xff0c;所以可以考虑跑多次网络流。 但跑同样的网络流没有意义&#xff0c;所以每次跑完都要在残余网络上操作一下才可行。此题中…

JVM理论知识

一、JVM内存结构 java的内存模型主要分为5个部分&#xff0c;分别是&#xff1a;JVM堆、JVM栈、本地栈、方法区还有程序计数器&#xff0c;他们的用途分别是&#xff1a; JVM堆&#xff1a;新建的对象都会放在这里&#xff0c;他是JVM中所占内存最大的区域。他又分为新生区还…

项目---日志系统

目录 项目系统开发环境核心技术日志系统介绍为什么需要日志系统? 日志系统框架设计日志系统模块划分代码实现通用工具实现日志等级模块实现日志消息模块实现格式化模块实现落地模块实现日志器模块同步日志器异步日志器缓冲区实现异步工作器实现 回归异步日志器模块建造者模式日…

【JavaEE】Spring事务-事务的基本介绍-事务的实现-@Transactional基本介绍和使用

【JavaEE】Spring事务&#xff08;1&#xff09; 文章目录 【JavaEE】Spring事务&#xff08;2&#xff09;1. 为什么要使用事务2. Spring中事务的实现2.1 事务针对哪些操作2.2 MySQL 事务使用2.3 Spring 编程式事务&#xff08;手动挡&#xff09;2.4 Spring 声明式事务&#…

分享一种针对uni-app相对通用的抓包方案

PART1&#xff0c;前言 近年来混合开发APP逐渐成为主流的开发模式&#xff0c;与传统的开发模式相比混合开发极大的提升了开发效率&#xff0c;同时跨平台的特性也降低了开发成本&#xff0c;一直以来混合开发被诟病的性能问题随着技术的发展也得到改善。技术的发展往往是一把…

基于FPGA的Lorenz混沌系统verilog开发,含testbench和matlab辅助测试程序

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 5.算法完整程序工程 1.算法运行效果图预览 将vivado的仿真结果导入到matlab显示三维混沌效果&#xff1a; 2.算法运行软件版本 vivado2019.2 matlab2022a 3.部分核心程序 testbench如下所…

4.15 TCP Keepalive 和 HTTP Keep-Alive 是一个东西吗?

目录 HTTP 的 Keep-Alive TCP 的 Keepalive 总结&#xff1a; HTTP的Keep-Alive&#xff0c;是应用层&#xff08;用户态&#xff09;实现的&#xff0c;称为HTTP长连接&#xff1b; TCP的Keepalive&#xff0c;是由TCP层&#xff08;内核态&#xff09;实现的&#xff0c;…

下载的文件被Windows 11 安全中心自动删除

今天从CSDN上下载了自己曾经上传的文件&#xff0c;但是浏览器下载完之后文件被Windows安全中心自动删除&#xff0c;说是带病毒。实际是没有病毒的&#xff0c;再说了即便有病毒也不应该直接删除啊&#xff0c;至少给用户一个保留或删除的选项。 研究了一番&#xff0c;可以暂…

2023-8-25 最大异或对

题目链接&#xff1a;最大异或对 #include <iostream> #include <algorithm>using namespace std;const int N 100010, M 31 * N;int a[N]; int son[M][2], idx;void insert(int x) {int p 0;for(int i 30; i > 0; i --){int u x >> i & 1;if(…

求生之路2私人服务器开服搭建教程centos

求生之路2私人服务器开服搭建教程centos 大家好我是艾西&#xff0c;朋友想玩求生之路2(left4dead2)重回经典。Steam玩起来有时候没有那么得劲&#xff0c;于是问我有没有可能自己搭建一个玩玩。今天跟大家分享的就是求生之路2的自己用服务器搭建的一个心路历程。 &#xff0…

如何把本地项目上传github

一、在gitHub上创建新项目 【1】点击添加&#xff08;&#xff09;-->New repository 【2】填写新项目的配置项 Repository name&#xff1a;项目名称 Description &#xff1a;项目的描述 Choose a license&#xff1a;license 【3】点击确定&#xff0c;项目已在githu…

课程项目设计--spring security--认证管理功能--宿舍管理系统--springboot后端

写在前面&#xff1a; 还要实习&#xff0c;每次时间好少呀&#xff0c;进度会比较慢一点 本文主要实现是用户管理相关功能。 前文项目建立 文章目录 验证码功能验证码配置验证码生成工具类添加依赖功能测试编写controller接口启动项目 security配置拦截器配置验证码拦截器 …