当前位置：首页 > news >正文

2021 CCF CSP-S2.廊桥分配

news 来源：原创 2025/8/15 8:34:53

题目

4090. 廊桥分配
在这里插入图片描述

算法标签: 模拟, 贪心, 堆

思路

可以将每个飞机的起始时间和离开时间看作一个线段, 每个廊桥在同一时间只能服务一架飞机, 因为先到先得因此是按照起始时间进行排序

每个廊桥只关心最后一架飞机离开的时刻, 对于每个飞机有开始时间和离开时间, 对于每个空闲的廊桥来说, 安排到任意一个廊桥都是一样的, 朴素的做法是枚举国内分配廊桥的数量, 再枚举飞机, 但是时间复杂来到了 $105 \times 10 ^ 5$ , 需要进行优化

因为放置到每个空闲廊桥是一样的, 因此可以按照廊桥编号从小到大放置飞机, 然后枚举分配给国内航班的廊桥数量, 维护两个小根堆分别代表使用的廊桥和空闲的廊桥, 时间复杂度 $O(n\log n)$

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>using namespace std;const int N = 10010, M = 50010, K = 19, INF = 0x3f3f3f3f;int n, m, q;
int head[N], ed[N << 1], ne[N << 1], w[N << 1], idx;
// 求路径上信息使用倍增优化
int fa[N][K], f[N][K], depth[N];
int p[N];
struct Edge {int u, v, w;bool operator< (const Edge &e) const {return w > e.w;}
} edges[M];void add(int u, int v, int val) {ed[idx] = v, ne[idx] = head[u], w[idx] = val, head[u] = idx++;
}int find(int u) {if (p[u] != u) p[u] = find(p[u]);return p[u];
}void kruskal() {sort(edges, edges + m);for (int i = 0; i < m; ++i) {auto [u, v, w] = edges[i];int fa1 = find(u);int fa2 = find(v);if (fa1 == fa2) continue;p[fa2] = fa1;add(u, v, w), add(v, u, w);}
}void dfs(int u, int pre, int dep) {depth[u] = dep;for (int i = head[u]; ~i; i = ne[i]) {int v = ed[i];if (v == pre) continue;fa[v][0] = u;f[v][0] = w[i];for (int k = 1; k < K; ++k) {int mid = fa[v][k - 1];fa[v][k] = fa[mid][k - 1];f[v][k] = min(f[v][k - 1], f[mid][k - 1]);}dfs(v, u, dep + 1);}
}int calc(int u, int v) {if (find(u) != find(v)) return -1;int ans = INF;if (depth[u] < depth[v]) swap(u, v);for (int k = K - 1; k >= 0; --k) {if (depth[fa[u][k]] >= depth[v]) {ans = min(ans, f[u][k]);u = fa[u][k];}}if (u == v) return ans;for (int k = K - 1; k >= 0; --k) {if (fa[u][k] != fa[v][k]) {ans = min({ans, f[u][k], f[v][k]});u = fa[u][k];v = fa[v][k];}}ans = min({ans, f[u][0], f[v][0]});return ans;
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);memset(head, -1, sizeof head);memset(f, 0x3f, sizeof f);cin >> n >> m;for (int i = 1; i <= n; ++i) p[i] = i;for (int i = 0; i < m; ++i) {int u, v, w;cin >> u >> v >> w;edges[i] = {u, v, w};}kruskal();for (int i = 1; i <= n; ++i) {if (depth[i] == 0) dfs(i, -1, 1);}cin >> q;while (q--) {int u, v;cin >> u >> v;int ans = calc(u, v);if (ans == INF) ans = -1;cout << ans << "\n";}return 0;
}

2021 CCF CSP-S2.廊桥分配

目录题目算法标签: 模拟, 贪心, 堆思路代码题目 4090. 廊桥分配算法标签: 模拟, 贪心, 堆思路可以将每个飞机的起始时间和离开时间看作一个线段, 每个廊桥在同一时间只能服务一架飞机, 因为先到先得因此是按照起始时间进行排序每个廊桥只关心最后一架飞机离开的时刻…...

编程日记 2025/8/15 8:34:53

博客标题栏添加一个 About Me

文章目录 ✅ 目标✍️ 第一步：创建 About 页面🧭 第二步：在导航栏添加菜单项🔄 第三步：重新启动本地服务🪄 可选美化：自定义样式💡 小贴士🎉 示例✅ 文件路径:✅ 页面代码…...

编程日记 2025/8/14 14:50:41

transient关键字深度解析

Java transient 关键字深度解析 1. 核心概念 (1) 基本定义作用：标记字段不参与序列化适用场景：敏感数据（如密码、密钥）临时计算字段依赖运行时环境的字段（如Thread对象） (2) 语法示例 java public class User implements Serializable {private String username…...

编程日记 2025/8/14 4:28:52

解决 pip install tts 报错问题-—SadTalker的AI数字人视频—未来之窗超算中心

pip install -r requirements.txt pip install TTS0.11.1 指定版本 pip install TTS0.11.1...

编程日记 2025/8/14 22:17:04

Java 数据类型全解析：基础、引用与包装类全面梳理

Java 中的数据类型分为两大类： 🧩 一、基本数据类型（Primitive Types） 共 8 种，分为数值类型、字符类型、布尔类型： 类型占用内存默认值说明byte1 字节0整数类型，范围 -128 ~ 127short2 字节…...

编程日记 2025/8/10 5:34:30

Linux计划任务详解：原理、优缺点及应用

Linux计划任务详解：原理、优缺点及应用文章目录 Linux计划任务详解：原理、优缺点及应用计划任务的基本原理Cron工作原理At工作原理计划任务的优缺点优点缺点 crontab 命令详解：用法与选项全指南基本语法常用选项详解1. 编辑 cron 任务 (-e)…...

编程日记 2025/8/13 23:37:09

MODBUS TCP 转 CANOpen

一、产品概述 1.1 产品用途 SG-TCP-COE-210 网关可以实现将 CANOpen 接口设备连接到 MODBUS TCP 网络中。用户不需要了解具体的 CANOpen 和 Modbus TCP 协议即可实现将 CANOpen 设备挂载到 MODBUS TCP 接口的 PLC 上，并和 CANOpen 设备进行数…...

编程日记 2025/8/10 14:16:59

00.IDEA 插件推荐清单（2025）

IDEA 插件推荐清单精选高效开发必备插件，提升 Java 开发体验与效率。参考来源：十六款好用的 IDEA 插件，强烈推荐！！！不容错过代码开发助手类插件名称功能简介推荐指数CodeGeeX智能代码补全、代码生成、…...

编程日记 2025/8/12 12:10:53

2D物体检测学习

DETR 1.提出了一种新的检测思路，将目标检测任务视作为集合预测问题 2.此前的检测器大都先用手工设计的候选框预测方案，例如anchor或滑动框。这些方案也包含了其他先验知识的干涉，例如NMS等后处理方案、anchor的设计、训练时如何将检测结果与…...

编程日记 2025/8/15 1:14:48

#手动控制windows更新时间(非常安全,可随时恢复)

HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\WindowsUpdate\UX\Settings 第一步: 点一下暂停更新第二步: 打开注册表,修改过期时间 ps: 若想恢复更新 , 只需要点"继续更新"...

编程日记 2025/8/14 0:01:41

SAP案例：珠海汉胜科技SAP S/4 HANA智能制造实践与价值实现

客户简介珠海汉胜科技股份有限公司为高科技生产企业，成立于1985年，拥有员工近2000人。主要从事生产、销售、研发：光纤光缆、电线、电缆及附件、铝塑复合管；光纤光缆、电缆、电线生产项目的策划及技术咨询。它致力于为国内外无线电…...

编程日记 2025/8/13 21:04:14

计算机视觉---相机标定

相机标定在机器人系统中的作用 1.确定相机的内部参数相机的内部参数包括焦距、主点坐标、像素尺寸等。这些参数决定了相机成像的几何关系。通过标定，可以精确获取这些参数，从而将图像中的像素坐标与实际的物理坐标建立联系。例如，已知相机…...

编程日记 2025/8/10 1:33:18

微信小程序的全局变量（quanjubianliang）

在微信小程序开发中，管理和使用全局变量是一种常见的需求。例如，可以通过小程序的App实例和globalData对象来实现全局变量的存储和共享。以下是详细说明： 1. 全局变量的定义微信小程序提供了 App() 函数，其中可以定义一个 global…...

编程日记 2025/8/14 23:06:33

Kotlin协程Semaphore withPermit约束并发任务数量

Kotlin协程Semaphore withPermit约束并发任务数量 import kotlinx.coroutines.* import kotlinx.coroutines.sync.Semaphore import kotlinx.coroutines.sync.withPermit import kotlinx.coroutines.launch import kotlinx.coroutines.runBlockingfun main() {val permits 1 /…...

编程日记 2025/8/11 18:33:03

LangChain, MCP Server, Qwen-Agent等测试及问题记录

LangChain LangGraph 参考官方文档：https://langchain-ai.github.io/langgraph/tutorials/introduction/ 1. 这里使用Qwen系列模型进行测试由于想测试通过LangGraph编排让大模型调用工具，所以首先查询支持Function Calling的大模型: https://help.a…...

编程日记 2025/8/13 6:55:20

学习设计模式《一》——简单工厂

一、基础概念 1.1、接口简单的说：接口是【用来实现类的行为定义、约束类的行为】（即：定义可以做什么）；接口可以包含【实例方法】、【属性】、【事件】、【索引器】或这四种成员类型的任意组合。接口的优点&#xff1…...

编程日记 2025/8/8 22:46:36

51单片机实验三:数码管动态显示

目录一、实验环境与实验器材二、实验内容及实验步骤 1. 数码管动态扫描0-5 2. 利用余辉效应使单片机数码管“同时显示”0-5。 3. B站小仿真（动态原理显示hello） 一、实验环境与实验器材环境：Keli，STC-ISP烧写软件,Proteus…...

编程日记 2025/8/7 5:31:06

[TriCore][TC3XX][用户手册] - 16.中断控制器 - IR

关键词： TC3XX 用户手册；TC3XX Interrupt Router；TC397 用户手册；TC397 中断控制器； 简介： 本篇为英飞凌 TC3XX 用户手册第 16 章翻译 - Interrupt Router (IR) 手册适用于 TC3XX（包括 TC397…...

编程日记 2025/8/13 2:22:06

Python语言基础教程（上）4.0

✨博客主页： https://blog.csdn.net/m0_63815035?typeblog 💗《博客内容》：.NET、Java.测试开发、Python、Android、Go、Node、Android前端小程序等相关领域知识 📢博客专栏： https://blog.csdn.net/m0_63815035/cat…...

编程日记 2025/8/14 22:53:54

快速入门smolagents

官方教程地址：Agents - Guided tour 1. 安装 pip install smolagents[litellm] 或者 uv add smolagents[litellm] 2. 配置api key 这里我用的火山的api，注意如果是使用的火山或阿里云的这种服务商的api，model_id这里要以"openai/&qu…...

编程日记 2025/8/11 6:15:47

第 3 期：逆过程建模与神经网络的作用（Reverse Process）

一、从正向扩散到逆向去噪：生成的本质在上期中我们讲到，正向扩散是一个逐步加入噪声的过程，从原始图像 x_0到接近高斯分布的 x_T： 而我们真正关心的，是从纯噪声中逐步还原原图的过程，也就是逆过程&…...

编程日记 2025/8/11 22:16:21

RAG-概述

RAG 概述 RAG（Retrieval Augmented Generation, 检索增强生成）是一种技术框架，其核心在于当 LLM 面对解答问题或创作文本任务时，首先会在大规模文档库中搜索并筛选出与任务紧密相关的素材，继而依据这些素材精准指导后续…...

编程日记 2025/8/11 17:29:00

Python 中的数据类型有哪些

Python 中的数据类型有哪些？ Python 是一种动态类型语言，支持多种内置数据类型，并且可以自定义数据类型。以下是 Python 中常见和重要的数据类型： 一、基本数据类型整数（int） 表示整数，没有小…...

编程日记 2025/8/12 20:53:17

梯度下降，共轭梯度，牛顿法，拟牛顿法的收敛速度对比

一、收敛速度理论对比方法收敛速度（一般非线性函数）收敛速度（二次凸函数）局部收敛性（接近极小点时）收敛阶梯度下降（GD）线性收敛（Linear）线性收敛&#xff0…...

编程日记 2025/8/13 6:42:03

深入浅出目标检测：从入门到YOLOv3，揭开计算机视觉的“火眼金睛”

目录揭开目标检测的神秘面纱什么是目标检测？为什么它如此重要？定义：图像分类、目标检测、目标跟踪、实例分割的区别与联系应用场景讲解目标检测的输出：边界框 (Bounding Box) 和类别 (Class)目标检测在AI领域的地位和发展趋势&…...

编程日记 2025/8/2 18:19:24

Odoo：免费开源的轧制品行业管理软件

Odoo免费开源的轧制品行业管理软件能够帮助建材、电线电缆、金属、造纸包装以及纺织品行业提高韧性和盈利能力，构筑美好未来。文 ｜ 开源智造（OSCG）Odoo金牌服务提高供应链韧性，赋能可持续发展如今，金属…...

编程日记 2025/8/10 18:25:58

51单片机实验六：通用型1602液晶操作方法

目录一、实验环境与实验器材二、实验内容及实验步骤 1. 目标：用C语言编程，实现在1602液晶的第一行显示“I LOVE MCU!”，在第二行显示WWW.TXMCU.COM。 2.目标：用C语言编程，实现第一行从右侧移入“Hello everyone!”…...

编程日记 2025/8/12 16:34:36

原型模式详解及c++代码实现(以自动驾驶感知场景为例)

模式定义原型模式（Prototype Pattern）是一种创建型设计模式，通过克隆已有对象来创建新对象，避免重复执行昂贵的初始化操作。该模式特别适用于需要高效创建相似对象的场景，是自动驾驶感知系统中处理大量重复数据结构的…...

编程日记 2025/8/14 16:37:48

datasheet数据手册-阅读方法

DataSheet Datasheet（数据手册）：电子元器件或者芯片的数据手册，一般由厂家编写，格式一般为PDF，内容为电子分立元器件或者芯片的各项参数，电性参数，物理参数，甚至制造材料…...

编程日记 2025/8/13 12:28:45

C言雅韵集：野指针

嘿，各位技术潮人！好久不见甚是想念。生活就像一场奇妙冒险，而编程就是那把超酷的万能钥匙。此刻，阳光洒在键盘上，灵感在指尖跳跃，让我们抛开一切束缚，给平淡日子加点料，注入满满的pa…...

编程日记 2025/8/7 23:34:13

2 celery环境搭建

1. 安装 Celery 及依赖 1.1 安装 Celery 使用 pip 安装 Celery（推荐 Python 3.7 环境）： pip install celery1.2 选择并安装 Broker Celery 需要一个消息中间件（Broker）来传递任务。以下是两种常用 Broker 的安装方…...

编程日记 2025/8/14 9:53:28

alertManager部署安装、告警规则配置详解及告警消息推送

java接受告警请求RestController RequestMapping("/alert") Slf4j public class TestApi {private static final DateTimeFormatter FORMATTER DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss");RequestMappingpublic void sendTemplate(HttpServl…...

编程日记 2025/8/11 3:11:52

day45——非递减数列（LeetCode-665）

题目描述给你一个长度为 n 的整数数组 nums ，请你判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 < i < n-2)，总满足 nums[i] < nums[i …...

编程日记 2025/8/11 4:44:04

LeetCode19.删除链表的倒数第N个节点

题目给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。请用一次扫描实现示例 1： 输入：head [1,2,3,4,5], n 2 输出：[1,2,3,5]示例 2： 输入：head [1], n 1 输出&#xff…...

编程日记 2025/8/10 20:07:07

Kafka系列之：计算kafka集群topic占的存储大小

Kafka系列之：计算kafka集群topic占的存储大小 topic存储数据格式统计topic存储大小定时统计topic存储大小topic存储数据格式单位是字节大小 size_bytes{directory="/data/datum/kafka/optics-all" } 782336计算topic存储大小脚本逻辑是：计算指定目录或文件的大小…...

编程日记 2025/8/11 19:16:17

Logisim数字逻辑实训——计数器设计与应用

4位递增计数器六进制计数器十进制计数器六十进制计数器二十四进制计数器计时器...

编程日记 2025/8/2 18:18:49

安卓手机如何改ip地址教程

对于安卓手机用户而言，ip修改用在电商、跨境电商、游戏搬砖、社交软件这些需要开多个账号的项目。因为多个设备或账号又不能在同一ip网络下，所以修改手机的IP地址防检测成为一个必要的操作。以下是在安卓手机上更改IP地址的多种方法及详细步骤&#xff0…...

编程日记 2025/8/2 18:18:47

论文阅读--Orient Anything

通过渲染3D模型来学习不同方向下物体的外观，并从单张和自由视角的图像中估计物体方向 1. 数据生成：基于 3D 渲染构建大规模方向标注数据集 - 数据来源： 使用 Objaverse 数据库中的高质量 3D 模型，进行筛选和预处理。 - 筛选规范…...

编程日记 2025/8/10 4:23:07

ASP.NET MVC 实现增删改查（CRUD）操作的完整示例

提供一个完整的 ASP.NET MVC 实现增删改查（CRUD）操作的示例。该示例使用 SQL Server 数据库，以一个简单的 Product 实体为例。步骤 1：创建 ASP.NET MVC 项目首先，在 Visual Studio 中创建一个新的 ASP.NET MVC 项目…...

编程日记 2025/8/9 15:53:59

ASP.NET常见安全漏洞及修复方式

Microsoft IIS 版本信息泄露查看网页返回的 Header 信息，默认会包含 IIS，ASP.NET 版本信息： 隐藏 Server 标头编辑 web.config 文件，在 system.webServer 节点中配置 requestFiltering 来移除Server标头： <sec…...

编程日记 2025/8/12 15:41:16

文件系统的npu和内核的npu有什么区别

我在编译rk3588的内核和文件系统时候，发现都编译到rknpu这个文件，那么文件系统的npu和内核的npu有什么根本的区别吗？ 我可以理解为，文件系统下是应用程序，内核下是驱动程序。功能定位内核中的 NPU 源码核心功能&am…...

编程日记 2025/8/6 6:31:38

RUI桌面TV版最新版免费下载-安卓电视版使用教程

在智能电视的使用中，拥有一款好用的桌面应用能极大提升体验，RUI桌面TV版就是这样一款实用的工具。下面为大家带来它的免费下载及安卓电视版使用教程。一、下载步骤首先确保你的安卓电视已连接网络。打开电视自带的应用商店，在搜索栏输入“…...

编程日记 2025/8/13 1:34:20

android的配置检查查看安卓设备配置

Android系统属性配置与内存管理指南在Android开发过程中，了解系统属性配置和内存管理机制对应用性能优化至关重要。本文将介绍如何通过adb命令查询和修改系统属性，以及如何合理管理应用内存。一、adb命令查询当前堆内存信息 1. 查询所有配置 adb s…...

编程日记 2025/8/11 13:34:13

RHCE的简单配置

一：配置qq第三方客户端验证 1.安装第三方邮件客户端软件 2.mail程序登录验证qq账号 3.在qq客户端程序（如浏览器中进入邮箱登录QQ邮箱->设置->账户）中通过设置开启imap/smtp服务提供第三方程序账号的授权码 4.因为需要 QQ 邮箱的 S…...

编程日记 2025/8/6 18:13:48

日语学习-日语知识点小记-构建基础-JLPT-N4阶段（7）：（1）ながら一边。。一边（2）。。。し。。。し。。又……又……

日语学习-日语知识点小记-构建基础-JLPT-N4阶段（7）：（1）ながら一边。。一边 （2）。。。し。。。し。。又……又…… 1、前言（1）情况说明（2）工程师…...

编程日记 2025/8/15 2:00:30

【图像梯度处理，图像边缘检测】图像处理（OpenCv）-part6

13 图像梯度处理 13.1 图像梯度边缘提取是图像处理中的一个重要任务，其目的是检测图像中灰度值发生显著变化的区域，这些区域通常对应于图像中的物体边界、纹理变化或深度变化等。边缘提取的原理可以分为以下几个关键步骤： 1. 边缘的定义和…...

编程日记 2025/8/9 18:15:12

一本通 2063：【例1.4】牛吃牧草 1005：地球人口承载力估计

Topic： Ideas： 为什么把这两道题放在一起呢？就是因为这两道题很类似，都是很简单的数学题，只要你会列出数学等式，你就学会这道题了！ 下面把计算过程展示给大家 Code： //2025/04/18…...

编程日记 2025/8/15 1:17:31

下载HBuilder X，使用uniapp编写微信小程序

到官网下载HBuilder X 地址：HBuilderX-高效极客技巧下载完成后解压打开解压后的文件夹找到HBuilderX.exe 打开显示更多，发送到桌面快捷方式到桌面上启动HBuilderX.exe启动应用在工具点击插件安装选择安装Vue3编译器点击新建创建Vue3项目编写项目…...

编程日记 2025/8/14 1:33:22

4.18---缓存相关问题（操作原子性，击穿，穿透，雪崩，redis优势）

为什么要用redis做一层缓存，相比直接查mysql有什么优势？ 首先介绍Mysql自带缓存机制的问题： MySQL 的缓存机制存在一些限制和问题,它自身带的缓存功能Query Cache只能缓存完全相同的查询语句，对于稍有不同的查询语句&#xff0c…...

编程日记 2025/8/8 0:18:47

前端：uniapp中uni.pageScrollTo方法与元素的overflow-y:auto之间的关联

在uniapp中，uni.pageScrollTo方法与元素的overflow-y:auto属性之间存在以下关联和差异： 一、功能定位差异 ‌uni.pageScrollTo‌ 属于‌页面级滚动控制‌，作用于整个页面容器‌34。要求页面内容高度必须超过屏幕高度，且由根元素下…...

编程日记 2025/8/15 1:25:02

目录

题目

算法标签: 模拟, 贪心, 堆

思路

代码

相关文章：