第十一次CCF-CSP认证(含C++源码)

第十一次CCF-CSP认证

  • 打酱油
    • 满分题解
  • 公共钥匙盒
    • 满分题解
      • solution 1
      • solution 2(优先队列优化)
  • 通信网络(图的遍历问题)
    • 满分题解

打酱油

在这里插入图片描述
题目链接

满分题解

思路:做完这题我觉得这里有点像贪心算法但又是常识性问题,
对于我拿到的钱金额为N,首先我确定全部用来买酱油,
我肯定想要用同样的钱买到尽可能多的酱油,所以这里我先尝试一下满5赠2,然后不满足满5赠2的条件之后,
剩余的钱假设为Q,我优先尝试能不能参加满3赠1,最后才是考虑用10块钱换一瓶酱油,
最后加起来就可以,我看了Y总的思路代码很短,但是我感觉我考试的时候还是喜欢用这种无脑的办法写哈哈哈,不想思考一点O(∩_∩)O哈哈~

#include <bits/stdc++.h>
using namespace std;
//基本思路:对于我们输入的N是小于300的一个10的倍数,我们可以先用N去余50,
//得到的余数再去余上30,如果还有那就直接处以10再加起来
int main()
{int n,p,q,a,b;cin>>n;if(n>=50){p=n%50;q=(n-p)/50;//得到能满足几次满五瓶送一瓶}else if(n<50){q=0;}if((n-50*q)>=30){a=(n-50*q)%30;b=(n-q*50-a)/30;}else if(n<30){b=0;}int sum=50*q+30*b;int res=(n-sum)/10+q*7+b*4;cout<<res;
}

公共钥匙盒

以往来说,第二题也就是一般的模拟,但是这题有些恶心了,我看了一下这次的平均分只有130左右,明显偏低的,所以这题能拿满已经比较靠前了,我觉得这题比较恶心的就是这取钥匙和还钥匙这个操作用代码怎么体现,怎么存储起来,特别是怎么样每次才能找到最左边的空挂钩呢,我觉得这是有些不太直白的地方,后来我想了一下,可以用一个结构体来存储每次的操作,至于题目中所体现的顺序问题,因为这里是结构体,需要我们自己重载一下小于号,也就是自己写一个cmp函数来制定规则
在这里插入图片描述
题目链接

满分题解

solution 1

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;// 定义常量 N 表示钥匙的最大数量
const int N = 1010;
// 数组 key 用于模拟钥匙盒,key[i] 表示第 i 个位置上的钥匙编号
int key[N];// 定义结构体 Node 用于存储钥匙的使用信息
struct Node 
{int id;  // 钥匙的编号int ti;  // 钥匙的使用时间(借用时间或归还时间)// 重载小于运算符,用于结构体的排序// 首先比较时间 ti,如果时间相同则比较钥匙编号 idbool operator<(const Node &t)const {if(ti == t.ti) return id < t.id;return ti < t.ti;}
};// 定义两个 Node 类型的数组,q1 存储钥匙的借用信息,q2 存储钥匙的归还信息
Node q1[N], q2[N];// n 表示钥匙的总数,m 表示借还钥匙的记录数
int n, m;int main()
{// 从标准输入读取钥匙的总数 n 和借还钥匙的记录数 mcin >> n >> m;// 初始化钥匙盒,将每个位置上的钥匙编号初始化为其位置编号for(int i = 1; i <= n; i ++) key[i] = i;// 循环读取 m 条借还钥匙的记录for(int i = 0; i < m; i ++){int a, b, c;// 读取钥匙编号 a、借用时间 b 和借用时长 ccin >> a >> b >> c;// 将借用信息存入 q1 数组q1[i] = {a, b};// 计算归还时间并将归还信息存入 q2 数组q2[i] = {a, b + c};}// 对借用信息数组 q1 按照时间和钥匙编号进行排序sort(q1, q1 + m);// 对归还信息数组 q2 按照时间和钥匙编号进行排序sort(q2, q2 + m);// 定义两个指针 i 和 j,分别用于遍历借用信息数组 q1 和归还信息数组 q2int i = 0, j = 0;// 当两个数组都未遍历完时,进行借还操作while (i < m && j < m){// 如果当前借用时间小于当前归还时间if(q1[i].ti < q2[j].ti){// 获取当前要借用的钥匙编号int id = q1[i].id;// 在钥匙盒中查找该钥匙并将其位置置为 0 表示已借出for(int k = 1; k <= n; k ++){if(key[k] == id)key[k] = 0;}// 移动借用信息数组的指针i ++;}// 如果当前借用时间大于等于当前归还时间else if(q1[i].ti >= q2[j].ti){// 获取当前要归还的钥匙编号int id2 = q2[j].id;// 在钥匙盒中查找第一个空闲位置并将钥匙归还到该位置for(int k = 1; k <= n; k ++){if(key[k] == 0){key[k] = id2;break;}}// 移动归还信息数组的指针j ++;}}// 处理可能剩余的未归还钥匙while(j < m){// 获取当前要归还的钥匙编号int id2 = q2[j].id;// 在钥匙盒中查找第一个空闲位置并将钥匙归还到该位置for(int k = 1; k <= n; k ++){if(key[k] == 0){key[k] = id2;break;}}// 移动归还信息数组的指针j ++;}// 输出最终钥匙盒中每个位置上的钥匙编号for(int k = 1; k <= n; k ++)cout << key[k] << ' ';cout << endl;return 0;
}

solution 2(优先队列优化)

其实我在读题目的时候就有点想用优先队列,主要是因为老师每次还钥匙的时候是按照一定规则的,上面的代码固然没问题,但是主要的瓶颈在于每次归还钥匙时,需要遍历钥匙盒来找到第一个空闲位置。

优化思路:
使用优先队列存储空闲位置:使用一个优先队列 available 来存储钥匙盒中的空闲位置,优先队列会自动按照位置编号从小到大排序。
优化借还操作:在借用钥匙时,将对应的钥匙位置从 key 数组中置为 0,并将该位置加入到优先队列 available 中;在归还钥匙时,从优先队列中取出最小的空闲位置,将钥匙归还到该位置。

示例说明
假设钥匙盒有 10 个位置,初始时所有位置都是空闲的,我们可以将位置编号 1 - 10 依次插入到优先队列中。当有钥匙被借用时,将对应的位置从优先队列中移除;当有钥匙归还时,直接从优先队列中取出队首元素(即编号最小的空闲位置),将钥匙归还到该位置。这样可以避免每次都遍历整个钥匙盒来查找空闲位置,从而提高程序的效率。

#include <iostream>
#include <algorithm>
#include <queue>using namespace std;const int N = 1010;
int key[N];struct Node {int id, ti;bool operator<(const Node& t) const {if (ti == t.ti) return id < t.id;return ti < t.ti;}
};Node q1[N], q2[N];
int n, m;int main() {cin >> n >> m;// 初始化钥匙盒for (int i = 1; i <= n; i++) key[i] = i;// 读取借还记录for (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;q1[i] = {a, b};q2[i] = {a, b + c};}// 对借用信息和归还信息进行排序sort(q1, q1 + m);sort(q2, q2 + m);// 优先队列,用于存储空闲位置priority_queue<int, vector<int>, greater<int>> available;// 初始时所有位置都是空闲的for (int i = 1; i <= n; i++) available.push(i);int i = 0, j = 0;while (i < m && j < m) {if (q1[i].ti < q2[j].ti) {// 借用钥匙int id = q1[i].id;for (int k = 1; k <= n; k++) {if (key[k] == id) {key[k] = 0;available.push(k);  // 将该位置标记为空闲break;}}i++;} else {// 归还钥匙int id2 = q2[j].id;int pos = available.top();  // 取出最小的空闲位置available.pop();key[pos] = id2;j++;}}// 处理剩余的未归还钥匙while (j < m) {int id2 = q2[j].id;int pos = available.top();  // 取出最小的空闲位置available.pop();key[pos] = id2;j++;}// 输出最终钥匙盒中每个位置上的钥匙编号for (int k = 1; k <= n; k++) {cout << key[k] << ' ';}cout << endl;return 0;
}

通信网络(图的遍历问题)

PS:第三题实在是太恶心了 我就跳过了,有能力的可以用C++写写看
这是第四题
在这里插入图片描述
题目链接

满分题解

思路参考(yxc):
给定一个有向图,判断图中哪些节点满足从该节点出发,通过正向图或反向图可以到达图中的所有其他节点。
说白了就是看一个点能不能到达所有点同时所有点也都能找到他
具体步骤如下:
1.构建邻接表:通过 add 函数构建正向图和反向图的邻接表。
2.深度优先搜索:对于每个节点,分别从该节点出发进行正向图和反向图的深度优先搜索,标记访问过的节点。
3.检查可达性:使用 check 函数检查是否所有节点都能从当前节点出发,通过正向图或反向图到达。
4.统计满足条件的节点数量:遍历所有节点,统计满足条件的节点数量并输出。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
// 定义常量 N 为最大节点数,M 为最大边数
const int N = 1e3 + 5, M = 1e4 + 5;// h 数组用于存储邻接表的头节点信息,二维数组中第二维 0 表示正向图,1 表示反向图
// e 数组用于存储边的终点信息,同样第二维区分正反向图
// ne 数组用于存储邻接表中每个节点的下一条边的编号,第二维区分正反向图
// cnt 数组用于记录正反向图中当前边的编号
int h[N][2], e[M][2], ne[M][2], cnt[2];
// st 数组用于标记节点是否被访问过,第二维区分正反向图
int st[N][2];// 向邻接表中添加边的函数
// u 是起点,v 是终点,type 表示图的类型(0 为正向图,1 为反向图)
void add(int u, int v, int type)
{// 新增一条边,边的编号为 cnt[type] 加 1e[++cnt[type]][type] = v;// 新边的下一条边是当前起点 u 的头边ne[cnt[type]][type] = h[u][type];// 更新起点 u 的头边为新边h[u][type] = cnt[type];
}// 深度优先搜索函数
// u 是当前搜索的节点,type 表示图的类型(0 为正向图,1 为反向图)
void dfs(int u, int type)
{// 遍历当前节点 u 的所有出边for (int i = h[u][type]; i; i = ne[i][type]){// 获取当前边的终点 vint v = e[i][type];// 如果终点 v 还未被访问过if (!st[v][type]){// 标记终点 v 为已访问st[v][type] = 1;// 从终点 v 继续进行深度优先搜索dfs(v, type);}}
}// 检查是否所有节点都能从某个节点出发,通过正向图或反向图到达
// n 是节点的总数
bool check(int n)
{// 遍历所有节点for (int i = 1; i <= n; ++i)// 如果某个节点在正向图和反向图中都未被访问过if (!st[i][0] && !st[i][1]) return false;// 所有节点都能通过正向图或反向图到达,返回 truereturn true;
}int main()
{int n, m;// 输入节点数 n 和边数 mscanf("%d%d", &n, &m);// 循环读取每条边的信息while (m--){int u, v;// 输入边的起点 u 和终点 vscanf("%d%d", &u, &v);// 向正向图中添加边 u -> vadd(u, v, 0);// 向反向图中添加边 v -> uadd(v, u, 1);}// 记录满足条件的节点数量int ret = 0;// 遍历所有节点for (int i = 1; i <= n; ++i){// 每次以不同节点为起点时,重置访问标记数组memset(st, 0, sizeof st);// 标记当前起点在正向图和反向图中都已访问st[i][0] = st[i][1] = 1;// 从当前起点开始进行正向图的深度优先搜索dfs(i, 0);// 从当前起点开始进行反向图的深度优先搜索dfs(i, 1);// 检查是否所有节点都能从当前起点出发,通过正向图或反向图到达if (check(n)) ret++;}// 输出满足条件的节点数量printf("%d", ret);return 0;
}

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

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

相关文章

深入解析Hosts文件:从原理到实战应用(文末附Qwins下载)

深入解析Hosts文件&#xff1a;从原理到实战应用 在网络世界中&#xff0c;一个看似普通的系统文件——Hosts文件&#xff0c;却隐藏着操控域名解析的“上帝权限”。无论是开发者的本地测试、网络安全防护&#xff0c;还是普通用户屏蔽广告&#xff0c;都离不开它的身影。本文将…

SpringBoot 和vue前后端配合开发网页拼图10关游戏源码技术分享

今天分享一个 前后端结合 的网页游戏 开发项目源码技术。 这也是我第一次写游戏类的程序&#xff0c;虽然不是特别复杂的游戏&#xff0c;但是是第一次写&#xff0c;肯定要记录一下了&#xff0c;哈哈。 游戏的内容 就是 我们显示中玩的那个 拼图碎片的 游戏&#xff0c;类似下…

TSB - AD 解读 — 迈向可靠、透明的 TSAD 任务

目录 一 文章动机 二 TSAD 领域内的两类缺陷 三 数据集的构建 四 实验结果及结论 项目宣传链接&#xff1a;TSB-AD 代码链接&#xff1a; TheDatumOrg/TSB-AD: TSB-AD: Towards A Reliable Time-Series Anomaly Detection Benchmark 原作者解读&#xff1a;NeurIPS 2…

Java 大视界 -- Java 大数据机器学习模型的对抗攻击与防御技术研究(137)

&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎来到 青云交的博客&#xff01;能与诸位在此相逢&#xff0c;我倍感荣幸。在这飞速更迭的时代&#xff0c;我们都渴望一方心灵净土&#xff0c;而 我的博客 正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识&#xff0c;也…

Python 鼠标轨迹算法 - 防止游戏检测

一.简介 鼠标轨迹算法是一种模拟人类鼠标操作的程序&#xff0c;它能够模拟出自然而真实的鼠标移动路径。 鼠标轨迹算法的底层实现采用C/C语言&#xff0c;原因在于C/C提供了高性能的执行能力和直接访问操作系统底层资源的能力。 鼠标轨迹算法具有以下优势&#xff1a; 模拟…

C++11 lambda表达式、包装器、Bind绑定

Hello&#xff01;大家早上中午晚上好&#xff01;&#xff01;今天来复习C11三个新加的特性&#xff01;&#xff01; 一、lambda 表达式 1.1什么是lambda表达式&#xff1f; 语法&#xff1a;[捕捉列表]&#xff08;参数列表&#xff09;->返回值{函数体}&#xff1b; …

计算机网络:(二)计算机网络在我国发展与网络类别与性能 (附带图谱更好对比理解)

计算机网络&#xff1a;&#xff08;二&#xff09;计算机网络在我国发展与网络类别和性能 前言一、计算机网络在我国的发展二、计算机网络的类别1. 计算机网络的定义2. 不同类别的计算机网络&#xff08;1&#xff09;按覆盖范围分类&#xff08;2&#xff09;按传输技术分类…

CoreData 调试警告:多个 NSEntityDescriptions 声明冲突的解决

概述 目前在苹果生态 App 的开发中&#xff0c;CoreData 数据库仍然是大部分中小应用的优先之选。不过&#xff0c;运行时 CoreData 常常产生各种“絮絮叨叨”的警告不禁让初学的秃头小码农们云里雾里。 这不&#xff0c;对于下面这一大段 CoreData 警告&#xff0c;大家是否一…

解决QT_Debug 调试信息不输出问题

方式1 &#xff1a;手动通过添加环境变量解决 ->使用命令&#xff1a; QT_LOGGING_TO_CONSOLE1 qtcreator启动 ->如若还未输出qDebug调试信息 则在程序中引<QLoggingCategory>包 #include <QLoggingCategory> ->在程序入口添加 QLoggingCategory::defa…

【CF】Day9——Codeforces Round 953 (Div. 2) BCD

B. New Bakery 题目&#xff1a; 思路&#xff1a; 被标签害了&#xff0c;用什么二分&#xff08; 很简单的思维题&#xff0c;首先如果a > b&#xff0c;那么全选a就行了&#xff0c;还搞啥活动 否则就选 b - a 天来搞活动&#xff0c;为什么&#xff1f; 首先如果我…

[MAVEN][经验总结]MAVEN_HOME和M2_HOME的配置建议

前言 MAVEN_HOME和M2_HOME都是maven的环境变量&#xff0c;要配置哪个&#xff0c;与maven版本有关&#xff0c;我在实操过程中遇到相关的问题&#xff0c;现记录如下。 MAVEN_HOME和M2_HOME的区别 MAVEN_HOME 和 M2_HOME 本质上是同一个作用的环境变量&#xff0c;它们的区…

力扣Hot100——169. 多数元素

解法1&#xff1a;使用HashMap 将nums数组映射到HashMap中&#xff0c;键为nums的值&#xff0c;值为nums中值的数量&#xff1b; 然后遍历哈希表&#xff0c;返回值最大的键 class Solution {private Map<Integer, Integer> countNums(int[] nums) {Map<Integer, Int…

EasyRTC嵌入式音视频通话SDK:微信生态支持、轻量化架构与跨平台兼容性(Linix/Windows/ARM/Android/iOS/LiteOS)

随着WebRTC技术的不断发展&#xff0c;实时音视频通信在各个领域的应用越来越广泛。EasyRTC嵌入式音视频通话SDK作为一款基于WebRTC技术的实时通信解决方案&#xff0c;凭借其强大的功能和灵活的集成能力&#xff0c;受到了越来越多开发者的关注。 一、系统架构设计 纯C语言开…

QuickAPI:一键将 Excel 数据转为数据库表

在开发和数据管理中&#xff0c;将 Excel 数据快速导入数据库是一项常见需求&#xff0c;但手动建表和导入的过程往往让人头疼。 QuickAPI 作为一款高效的统一数据服务平台&#xff0c;提供了一键将 Excel 数据转为数据库表的功能&#xff0c;极大简化了操作流程。本文将以技术…

【MySQL】多表查询(笛卡尔积现象,联合查询、内连接、左外连接、右外连接、子查询)-通过练习快速掌握法

在DQL的基础查询中&#xff0c;我们已经学过了多表查询的一种&#xff1a;联合查询&#xff08;union&#xff09;。本文我们将系统的讲解多表查询。 笛卡尔积现象 首先&#xff0c;我们想要查询emp表和stu表两个表&#xff0c;按照我们之前的知识栈&#xff0c;我们直接使用…

JavaScript如何做类型转换

一、类型转换 二、补充 console.log(1 "2" "2"); // 122 console.log(1 "2" "2"); // 32 console.log(1 -"1" "2"); // 02 console.log("1" "1" "2"); // 112 consol…

华为中小型企业项目案例

实验目的(1) 熟悉华为交换机和路由器的应用场景 (2) 掌握华为交换机和路由器的配置方法 实验拓扑实验拓扑如图所示。 华为中小型企业项目案例拓扑图 实验配置市场部和技术部的配置创建VLANLSW1的配置 [LSW1]vlan batch 10 20 [LSW1]q…

【PyTorch][chapter-35][MLA]

前言&#xff1a; MLA&#xff08;Multi-head Latent Attention&#xff0c;多头潜在注意力&#xff09;旨在提高推理效率和降低计算资源的消。MLA的核心思想在于通过信息转移来优化KV缓存的使用 MLA的技术特点主要包括&#xff1a; KV压缩与潜在变量&#xff1a;将键&#xff…

Spring Cloud 中的服务注册与发现: Eureka详解

1. 背景 1.1 问题描述 我们如果通过 RestTamplate 进行远程调用时&#xff0c;URL 是写死的&#xff0c;例如&#xff1a; String url "http://127.0.0.1:9090/product/" orderInfo.getProductId(); 当机器更换或者新增机器时&#xff0c;这个 URL 就需要相应地变…

微服务存在的问题及解决方案

微服务存在的问题及解决方案 1. 存在问题 1.1 接口拖慢 因为一个接口在并发时&#xff0c;正好执行时长又比较长&#xff0c;那么当前这个接口占用过多的 Tomcat 连接&#xff0c;导致其他接口无法即时获取到 Tomcat 连接来完成请求&#xff0c;导致接口拖慢&#xff0c;甚至…