第十五届蓝桥杯大赛软件赛省赛Python 大学 B 组试做(下)【本期题单: 缴纳过路费, 纯职业小组】
本期题单:缴纳过路费,纯职业小队
文章目录
- 缴纳过路费
- 题目
- 思路分析
- 代码
- 纯职业小组
- 题目
- 思路分析
- 感谢大伙观看,别忘了三连支持一下
- 大家也可以关注一下我的其它专栏,同样精彩喔~
- 下期见咯~
缴纳过路费
题目
题目链接:缴纳过路费
思路分析
这一题就是很典型的 并查集 的题目了,它就是一个找父节点的思路流程。
对于并查集,本篇就不说了,后面会出一期来讲它的,如果对这个算法陌生的话可以学习一下这个大佬的文章:跳转链接,这位大佬讲的很好,我也是学习的他的文章。
下面就针对这道题分析一下 ——
题目里面比较需要注意的点 ——
- 过路费是指最大价值,而不是总和
- 过路费要处于上下限之间
- 道路是双向的
规则一 和 规则二,就意味着如果有一条路的价值超过上限,那就不需要考虑它。对于低于下限的道路,可以和符合条件的道路共存,但不能单独存在。
规则三意味着没有直接连接的两个地方也能够到达。
OK,大概就是这些内容,然后我们针对下面这组数据来分析一下
6 8 2 7
1 2 2
1 3 5
2 3 8
1 4 1
2 4 5
2 5 4
3 4 9
2 6 1
其中 2 - 3 和 3 - 4这两条路超过了最大价值,可以在存储的时候直接去除掉,我们用不到它。
然后 1 - 4 和 2 - 6这两条路低于最低价值,我们需要记录一下,不能让它们单独出现。
uf1是低于上限的,uf2是低于下限的
他们的一个路径大致如下图 ——
也就是说——
(1,2)(1,3)(1,4)(1,5)(2,3)(2,4)(2,5)(3,4)(3,5)(4,5)
任选两个城市都是符合的,所以我们只需要知道符合的城市的总数,然后就能直接计算:
n * (n - 1) // 2
然后还需要注意类似uf2这样结构的,就是两个独立的分支,两边都需要计算。
低于上限的所有路径 - 只包含低于下限的路径
这样就能够计算上所有符合的了。
OKK,下面看看代码吧。
代码
class UnionFind:def __init__(self, n):self.pre = [i for i in range(n)] # 记录父节点self.size = [1] * ndef find(self, x): # 寻找根节点if x != self.pre[x]: # 判断父节点是不是自己本身rx = self.find(self.pre[x]) # 向上寻找父节点self.pre[x] = rxreturn rxreturn xdef union(self, x, y): # 组合/连接两个节点rx, ry = self.find(x), self.find(y)if rx == ry: # 如果两个数的父节点是相同的就直接返回returnself.pre[ry] = rx # 这里互换也是一样的,不考虑内部结构self.size[rx] += self.size[ry] # 记录以它为根节点的所有子树def cal(num):return num * (num - 1) // 2n, m, l, r = map(int, input().split())
uf1 = UnionFind(n + 1)
uf2 = UnionFind(n + 1)
for i in range(n):u, v, w = map(int, input().split())if w <= r: # 比上限小的才存进来uf1.union(u, v)if w < l:uf2.union(u, v)ans = 0
for i in range(1, n + 1):if i == uf1.find(i):ans += cal(uf1.size[i])if i == uf2.find(i):ans -= cal(uf2.size[i])
print(ans)
纯职业小组
题目
题目链接:纯职业小组
思路分析
这道题就是去考虑最差情况,题目情况很多,我们一点点来分析。
首先我们对各个小组人数进行一个分类 ——
- 比3小的,这个就直接加上去就行了
- 比3大的,余数是 0 的,如果被用完 + 0,没用完 + 2
- 比3大的,余数是 1 的,如果被用完 + 1,没用完 + 2
- 比3大的,余数是 2 的,这个无论有没有被用完,都可以直接 + 2
给大家一个例子
1
2 2
1 8
3 4
你们按照上面的逻辑去写,就知道怎么个事儿了。
然后对于 所能组成的队伍数 - k(需要组成的队伍数) 如果 大于兵种数,那么就需要加上 2 * 兵种数,如果小于兵种数就需要进行更麻烦的计算了。
if k <= y2:ans += 3 * k + (y0 + y1) * 2 + y2 * 2
elif k <= y1 + y2:x = y1 + y2 - kans += 3 * k + (y0 + x) * 2 + y2 * 2 + (y1 - x)
elif k <= y0 + y1 + y2:x = y0 + y1 + y2 - kans = 3 * k + x * 2 + y2 * 2 + y1
大概就是这么回事。
然后和大伙说一下就是我的代码没有完全实现,至少在我对这道题目的理解下,但是能够解决题目测试点,但是整体思路应该是对的。
t = int(input())
for _ in range(t):n, k = map(int, input().split())A = {}z = 0for __ in range(n):a, b = map(int, input().split())if a in A.keys():A[a] += belse:A[a] = bgroup = ans = 0y0 = y1 = y2 = 0for i in A.keys():if A[i] >= 3:group += A[i] // 3if A[i] % 3 == 0: # 余数为0y0 += 1elif A[i] % 3 == 1: # 余数为1y1 += 1elif A[i] % 3 == 2: # 余数为2y2 += 1else:ans += A[i] # 比3小的队伍直接加z += 1if k > group:print(-1)else:if group - k > n: # 测试样例全是这里的值ans += k * 3 + 2 * (len(A.keys()) - z)print(ans - 2)else:if k <= y2:ans += 3 * k + (y0 + y1) * 2 + y2 * 2elif k <= y1 + y2:x = y1 + y2 - kans += 3 * k + (y0 + x) * 2 + y2 * 2 + (y1 - x)elif k <= y0 + y1 + y2:x = y0 + y1 + y2 - kans = 3 * k + x * 2 + y2 * 2 + y1print(ans)
感谢大伙观看,别忘了三连支持一下
大家也可以关注一下我的其它专栏,同样精彩喔~
下期见咯~
相关文章:
第十五届蓝桥杯大赛软件赛省赛Python 大学 B 组试做(下)【本期题单: 缴纳过路费, 纯职业小组】
本期题单:缴纳过路费,纯职业小队 文章目录 缴纳过路费题目思路分析代码 纯职业小组题目思路分析 感谢大伙观看,别忘了三连支持一下大家也可以关注一下我的其它专栏,同样精彩喔~下期见咯~ 缴纳过路费 题目 题目链接:缴…...
【Hadoop入门】Hadoop生态之Oozie简介
1 什么是Oozie? Oozie是Apache基金会下的一个开源工作流调度系统,专门设计用于管理Hadoop作业。作为一个基于工作流的调度服务器,它能够在复杂的任务依赖关系中协调Hadoop MapReduce、Pig、Hive等任务的执行,是大数据平台中任务编…...
【Amazon EC2】为何基于浏览器的EC2 Instance Connect 客户端连接不上EC2实例
文章目录 前言📖一、报错先知❌二、问题复现😯三、解决办法🎲四、验证结果👍五、参考链接🔗 前言📖 这篇文章将讲述我在 Amazon EC2 上使用 RHEL9 AMI 时无法连接到 EC2 实例时所遇到的麻烦😖 …...
【大模型系列篇】最强检索增强技术GraphRAG基本原理详解
GraphRAG是一种结合了知识图谱(Knowledge Graph)和大型语言模型(Large Language Model, LLM)的检索增强生成(Retrieval-Augmented Generation, RAG)技术。它通过引入图结构化的知识表示和处理方法ÿ…...
【高阶数据结构】第二弹---图的深度解析:从基本概念到邻接矩阵的存储与操作
✨个人主页: 熬夜学编程的小林 💗系列专栏: 【C语言详解】 【数据结构详解】【C详解】【Linux系统编程】【高阶数据结构】 目录 1、图的基本概念 2、图的存储结构 2.1、邻接矩阵 2.1.1、基本结构 2.1.2、图的创建 2.1.3、获取顶点下标…...
【Java实战】——手撕斐波那契数列
🎁个人主页:User_芊芊君子 🎉欢迎大家点赞👍评论📝收藏⭐文章 🔍系列专栏:【Java】内容概括 这里写目录标题 1.什么是斐波那契数列?2.代码实现2.1 递归实现2.2 迭代实现 3.执行结果 …...
Python数据可视化-第7章-绘制3D图表和统计地图
环境 开发工具 VSCode库的版本 numpy1.26.4 matplotlib3.10.1 ipympl0.9.7教材 本书为《Python数据可视化》一书的配套内容,本章为第7章 绘制3D图表和统计地图 本章首先介绍了使用mplot3d工具包绘制3D图表,然后介绍了使用animation模块制作动画&#…...
操作系统 4.2-键盘
键盘中断初始化和处理 提取的代码如下: // con_init 函数,初始化控制台(包括键盘)的中断 void con_init(void) {set_trap_gate(0x21, &keyboard_interrupt); } // 键盘中断处理函数 .globl _keyboard_interrupt _keyboard…...
24.0.2 双系统ubuntu 安装显卡驱动黑屏,系统启动界面键盘失灵
问题描述:通过run文件在ubuntu 界面版安装nvidia 驱动后,忽然黑屏,再次启动时,键盘鼠标失灵无法选择系统,只能进入ubuntu界面。第二个问题是ubuntu 也无法用户登录,左上角光标闪烁。 查询方案,…...
探索多领域免费API资源库:打造数据查询利器
在当今信息爆炸的时代,获取各种领域的数据已成为许多人的需求。而免费API资源库的出现为我们提供了便捷的途径,让我们可以轻松地获取所需数据。本文将介绍涵盖20领域的免费API资源库,通过代码示例展示其功能,帮助读者更好地理解和…...
jenkins项目发布-安装k8s(rancher)客户端kubectl
找一台Linux 上安装 kubectl 以下是通过国内镜像源快速安装 kubectl 的方法,适合国内网络环境。 1. 下载 kubectl 通过国内镜像源下载指定版本的 kubectl: 使用阿里云镜像源下载: curl -LO "https://dl.k8s.io/release/$(curl -L -…...
【2025年认证杯数学中国数学建模网络挑战赛】C题 数据预处理与问题一二求解
目录 2025认证杯网络挑战赛A题 数据预处理与问题一求解三、数据预处理及分析3.1 数据可视化3.2 滑动窗口相关系数统计与动态置信区间耦合分析模型3.3 耦合关系分析结果 四、问题一代码数据预处理问题一 2025认证杯网络挑战赛 A题 数据预处理与问题一求解 三、数据预处理及分析…...
天玑AI开发套件2.0模型库数量激增3.3倍,让AI开发选择更自由
AI终端能力的升级,从不止步于硬件性能的提升,更有赖于软硬一体的系统化能力建设。在MDDC 2025大会上,联发科整合发布AI游戏两大核心场景下的开发平台:Neuron Studio打通模型开发全流程;Dimensity Profiler从多个维度提…...
edge 更新到135后,Clash 打开后,正常网页也会自动跳转
发现了一个有意思的问题:edge 更新135后,以前正常使用的clash出现了打开deepseek也会自动跳转: Search Resultshttps://zurefy.com/zu1.php#gsc.tab0&gsc.qdeepseek ,也就是不需要梯子的网站打不开了,需要的一直正…...
Socket多路复用网络编程应用总结
Socket多路复用网络编程应用总结 概述 • 传统I/O模型的局限性:传统阻塞式I/O模型每次仅在一个文件描述符(File Descriptor, FD)上执行I/O操作,导致程序需等待单个操作完成,无法高效处理多连接场景(如高并…...
APT攻击阶段划分,每个阶段分区方法
根据现有资料,APT(高级持续性威胁)攻击的阶段划分主要基于两种主流模型:洛克希德-马丁的杀伤链模型和生命周期模型。以下是分阶段详解及分区依据: 一、洛克希德-马丁杀伤链模型(7阶段) 核心逻辑…...
图像颜色空间对比(Opencv)
1. 颜色转换 import cv2 import matplotlib.pyplot as plotimg cv2.imread("tmp.jpg") img_r cv2.cvtColor(img, cv2.COLOR_BGR2RGB) img_g cv2.cvtColor(img, cv2.COLOR_BGR2GRAY) img_h cv2.cvtColor(img, cv2.COLOR_BGR2HSV) img_l cv2.cvtColor(img, cv2.C…...
【NLP 58、利用trl框架训练LLM】
孤独总比忍受傻逼好得多 —— 25.4.11 源代码网页: 项目文件预览 - trl:Train transformer language models with reinforcement learning. - GitCode TRL —— 变压器强化学习 trl:一个用于后训练基础模型的全面库 1.概述 TRL 是一个利用监督微调&a…...
数据仓库元数据的管理
元数据(Meta Date),主要记录数据仓库中模型的定义、各层级间的映射关系、监控数据仓库的数据状态 及ETL的任务运行状态。一般会通过元数据资料库(Metadata Repository)来统一地存储和管理元数据,其主要 目的…...
MySQL逻辑架构有什么?
1. MySQL逻辑架构分层 MySQL的逻辑架构可分为三层(自上而下): 连接层(Client Layer)服务层(Server Layer)存储引擎层(Storage Engine Layer) -----------------------…...
蓝桥杯 web 常用到的一些知识点
reduce 方法遍历数组、将数组元素累计 ①reduce接收两个参数,一个回调函数,一个初始值 ②回调函数传递了两个参数,一个是累加值,另一个是当前值 reduce的写法: arrays.reduce((a,cÿ…...
构建高可靠C++服务框架:从日志系统到任务调度器的完整实现
构建高可靠C服务框架:从日志系统到任务调度器的完整实现 一、深度解析示例代码技术体系 1.1 日志系统的进阶应用 示例代码中的ZRY_LOG_XXX宏展示了基础日志功能,但在生产环境中我们需要更完善的日志系统: 推荐技术栈组合: sp…...
<C#>在 C# .NET 中,使用 LoggerExtensions方法创建日志
在 C# .NET 中,LoggerExtensions 是 Microsoft.Extensions.Logging 命名空间下的一组扩展方法,它们为 ILogger 接口提供了便捷的日志记录方式。借助这些扩展方法,你能轻松记录不同级别的日志,如调试信息、信息、警告、错误等。下面…...
微服务与Spring Cloud Alibaba简介
微服务(或微服务架构)是一种云原生架构方法,其中单个应用程序由许多松散耦合且可独立部署的较小组件或服务组成。本单元主要介绍微服务架构的定义、微服务的特征、微服务架构面临的挑战、Spring Cloud 定义、Spring Cloud 核心组件、Spring C…...
元生代品牌建设:平台实现工作流(comfyui)创建与技术文档说明
本文摘要:蓝耘科技自2004年成立以来,从传统IT系统集成业务转型为聚焦GPU算力云服务的科技公司。其发布的元生代平台,是一个集算力调度、应用市场和AI协作开发为一体的智算云平台。用户可在蓝耘平台使用ComfyUI进行AI绘图,通过添加…...
无线通信网
1.2.4G相邻信道间有干扰,5G相邻信道几乎无干扰 2.2.4G频段的优点是信号强,衰减小,穿墙强,覆盖距离远;缺点是带宽较窄,速度较慢,干扰较大。 5G频段的优点是带宽较宽,速度较快&#…...
WMware虚拟机Ubuntu磁盘扩容
VMware中操作: 选择要扩容的虚拟机,点击编辑虚拟机设置 打开后点击磁盘——>点击扩展(注意:如果想要扩容的话需要删除快照) 调整到你想要的容量 点击上图的扩展——>确定 然后我们进到虚拟机里面 首先&#…...
vscode头文件自由跳转
文章目录 1. 安装c/c扩展2. 建.vscode文件夹 当你想要ctl鼠标左击跳转到三方库的定义的时候请往下看。 1. 安装c/c扩展 2. 建.vscode文件夹 在.vscode文件夹下新建c_cpp_properties.json {"configurations": [{"name": "Linux","include…...
BUG:Cannot find implementation for xxx. database. xxx. xxx_Impl does not exist
问题背景 使用Jetpack Compose将数据存储在room本地数据库时,编译报错: java. lang. RuntimeException: Cannot find implementation for com. example. androidproject. practice. roomdmeo. database. AppDatabase. AppDatabase_Impl does not exist …...
基于PySide6与pyCATIA的工程图智能文本替换工具开发指南
一、需求背景与实现价值 在汽车、航空等制造领域,CATIA工程图的文本标注管理常面临批量修改需求。传统手工操作存在效率低、易出错等问题。本文实现的文本替换工具具有以下行业价值: 提升图纸修订效率(单次操作可处理数千个文本对象&#x…...
MCP协议下人工智能康复理疗智械融合编程方向分析
一、引言:AI 康复时代的技术革新 在全球人口老龄化进程加速以及慢性病发病率持续走高的双重背景下,康复医疗领域正面临着前所未有的需求增长压力。据世界卫生组织(WHO)相关数据表明,预计到 2050 年,全球 60 岁及以上老年人口数量将激增至 21 亿,这一庞大群体中,绝大多…...
【嵌入式硬件】LAN9253说明书(中文版)
目录 1.介绍 1.1总体介绍 1.2模式介绍 1.2.1微控制器模式: 1.2.2 扩展模式 1.2.3 数字IO模式 1.2.4 各模式图 2.引脚说明 2.1 引脚总览 2.2 引脚描述 2.2.1 LAN端口A引脚 2.2.2 LAN端口B引脚 2.2.3 LAN端口A和、B电源和公共引脚 2.2.4 SPI/SQI PINS 2.2.5 分布式时…...
Java学习手册:Java基本语法与数据类型
Java语言以其简洁明了的语法和强大的数据类型系统而闻名。掌握Java的基本语法和数据类型是成为一名合格Java开发者的第一步。本文将深入探讨Java的基本语法结构和数据类型,帮助读者打下坚实的基础。 Java的基本语法 Java语言的语法设计简洁而强大,强调…...
操作系统 3.4-段页结合的实际内存管理
段与页结合的初步思路 虚拟内存的引入: 为了结合段和页的优势,操作系统引入了虚拟内存的概念。虚拟内存是一段地址空间,它映射到物理内存上,但对用户程序是透明的。 段到虚拟内存的映射: 用户程序中的段首先映射到虚…...
金融简单介绍及金融诈骗防范
在当今社会,金融学如同一股无形却强大的力量,深刻影响着我们生活的方方面面。无论是个人的日常收支、投资理财,还是国家的宏观经济调控,都与金融学紧密相连。 一、金融学的概念 金融学,简单来说,是研…...
基于docker搭建redis集群环境
在redis目录下创建redis-cluster目录,创建docker-compose.yml文化和generate.sh文件 【配置generate.sh文件】 for port in $(seq 1 9); \ do \ mkdir -p redis${port}/ touch redis${port}/redis.conf cat << EOF > redis${port}/redis.conf port 6379 …...
CSS 中常见的布局相关属性及其功能分类
一、块级布局(Block Layout) 1. display 作用:定义元素的显示方式。常用值: block:块级元素,默认独占一行。inline:行内元素,与其他内容在同一行显示。inline-block:兼…...
用css画一条弧线
ui里有一条弧线,现在用css实现 关键代码 border-bottom-left-radius: 100% 7px 两个参数分别代表横向和纵向的深度border-bottom-right-radius: 100% 7px...
CesiumForUnreal 本地矢量文件的加载,支持 shp/geojson 等常用格式
实现效果 Cesium for Unreal 集成 GDAL、LibPng 实现加载本地矢量文件 实现步骤 添加依赖在 cesium-unreal 中 extern -> cesium-native -> CMakeLists.txt 中的 57 行添加依赖库,代码如下: set(PACKAGES_PRIVATEabseil draco ktx modp-base64 meshoptimizer openssl …...
面向基于发布-订阅的物联网网络的匿名 MQTT 分析
中文标题: 面向基于发布-订阅的物联网网络的匿名 MQTT 分析 英文标题: An Analysis of Anonymous MQTT for Publish-Subscribe-Based IoT Networks 作者信息 Yudai Fukushima:东京都立大学电气工程与计算机科学系硕士生,研究方向…...
<C#> 详细介绍.NET 依赖注入
在 .NET 开发中,依赖注入(Dependency Injection,简称 DI)是一种设计模式,它可以增强代码的可测试性、可维护性和可扩展性。以下是对 .NET 依赖注入的详细介绍: 1. 什么是依赖注入 在软件开发里࿰…...
批量给文件编排序号,支持数字序号及时间日期序号编排文件
当我们需要对文件进行编号的时候,我们可以通过这个工具来帮我们完成,它可以支持从 001 到 100 甚至更多的数字序号编号。也可以支持按照日期、时间等方式对文件进行编号操作。这是一种操作简单,处理起来也非常的高效文件编排序号的方法。 工作…...
乳腺癌识别:双模型融合
本文为为🔗365天深度学习训练营内部文章 原作者:K同学啊 import matplotlib.pyplot as plt import tensorflow as tf import warnings as w w.filterwarnings(ignore) # 支持中文 plt.rcParams[font.sans-serif] [SimHei] # 用来正常显示中文标签 …...
ubuntu 22.04配置cuda和cudnn
cuda:12.1 wget https://developer.download.nvidia.com/compute/cuda/12.1.1/local_installers/cuda_12.1.1_530.30.02_linux.run sudo sh cuda_12.1.1_530.30.02_linux.runAbort/Continue选择Continue,不要勾选自带的driver 配置环境变量。~/.bashrc e…...
为什么Java不支持多继承?如何实现多继承?
一、前言 Java不支持多继承(一个类继承多个父类)主要出于文中设计考虑;核心目的是简化语言复杂性并避免潜在的歧义性问题。 二、直接原因:菱形继承/钻石继承问题(Diamond Problem) 假设存在如下继承关系&…...
ESP32S3 链接到 WiFi
以下是关于如何让 ESP32S3 连接到 WiFi 的完整流程和代码示例: ESP32S3 链接到 WiFi 1. 设置工作模式 ESP32 可以工作在两种模式下: Station (STA) 模式:作为无线终端连接到无线接入点(AP),类似于手机或…...
AndroidTV D贝桌面-v3.2.5-[支持文件传输]
AndroidTV D贝桌面 链接:https://pan.xunlei.com/s/VONXSBtgn8S_BsZxzjH_mHlAA1?pwdzet2# AndroidTV D贝桌面-v3.2.5[支持文件传输] 第一次使用的话,壁纸默认去掉的,不需要按遥控器上键,自己更换壁纸即可...
在spark中,窄依赖算子map和filter会组合为一个stage,这种情况下,map和filter是在一个task内进行的吗?
在 Spark 中,当 map 和 filter 这类窄依赖(Narrow Dependency)的算子连续应用时,它们会被合并到同一个 Stage 中,并且在同一个 Task 内按顺序执行。这种优化称为 流水线(Pipeline)执行ÿ…...
展讯android15源码编译之apk单编
首先找到你要单编的apk生成的路径: sys\out_system\target\product\ussi_arm64\system_ext\app\HelloDemo\HelloDemo.apk接着打开下面这个文件: sys\out_system\ussi_arm64_full-userdebug-gms.system.build.log在里面找关键字"Running command&q…...
EtherCAT 转 ModbusTCP 网关
一、功能概述 1.1 设备简介 本产品是 EtherCAT 和 Modbus TCP 网关,使用数据映射方式工作。 本产品在 EtherCAT 侧作为 EtherCAT 从站,接 TwinCAT 、 CodeSYS 、 PLC 等;在 ModbusTCP 侧做为 ModbusTCP 主站( C…...