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

(蓝桥杯——10. 小郑做志愿者)洛斯里克城志愿者问题详解

题目背景

小郑是一名大学生,她决定通过做志愿者来增加自己的综合分。她的任务是帮助游客解决交通困难的问题。洛斯里克城是一个六朝古都,拥有 N 个区域和古老的地铁系统。地铁线路覆盖了树形结构上的某些路径,游客会询问两个区域是否可以通过某条地铁线路直达,以及有多少条这样的线路。小郑需要快速回答这些问题,否则可能会失去志愿者工时。


问题描述

  1. 输入

    • N: 洛斯里克城的区域数。
    • M: 地铁线路的数量。
    • Q: 游客的询问数量。
    • N−1 条轨道:连接 N 个区域形成一棵树。
    • M 条地铁线路:每条线路覆盖树上某两点之间的最短路径。
    • Q 个游客询问:每个询问给出两个区域 (p,q),问它们是否在某条地铁线路上,如果是,统计有多少条这样的线路。
  2. 输出

    • 对于每个询问,输出满足条件的地铁线路数量。

解题思路

1. 树的基本性质

洛斯里克城的区域构成了一棵树(无环连通图),具有以下性质:

  • 任意两点之间有且仅有一条简单路径。
  • 可以通过深度优先搜索(DFS)或广度优先搜索(BFS)遍历树,计算每个节点的深度和父节点关系。
  • 最近公共祖先(LCA)可以帮助我们快速找到两点之间的路径。

2. 地铁线路的路径覆盖

每条地铁线路覆盖了树上某两点之间的最短路径。为了判断某个点对 (p,q) 是否被某条地铁线路覆盖,我们需要:

  • 找到地铁线路的起点和终点。
  • 计算这条线路覆盖的所有点对,并记录这些点对被多少条地铁线路覆盖。

3. 游客询问的处理

对于每个询问 $(p, q)$:

  • 如果 p>q,交换 p 和 q,确保点对有序。
  • 查询点对 (p,q) 被多少条地铁线路覆盖。

算法设计

方法一:

1. 构建树结构

代码

graph = defaultdict(list)for _ in range(N - 1):u, v = map(int, input().strip().split())graph[u].append(v)graph[v].append(u)

功能

  • 使用 defaultdict(list) 构建无向图的邻接表。

  • 每条轨道连接两个区域 u 和 v,因此需要将 v 添加到 u 的邻居列表中,同时将 u 添加到 v 的邻居列表中。

示例

假设输入如下轨道信息:

复制

1 2

2 3

1 4

构建的邻接表为:

作用

  • 邻接表表示了树的结构,方便后续通过 DFS 找到任意两点之间的路径。


2. 存储地铁线路

代码

subway_lines = []for _ in range(M):a, b = map(int, input().strip().split())subway_lines.append((a, b))

功能

  • 将每条地铁线路的起点 a 和终点 b 存储为元组 (a, b),并添加到列表 subway_lines 中。

示例

假设输入如下地铁线路:

作用

  • 地铁线路的起点和终点用于后续查找路径覆盖情况。


3. 深度优先搜索(DFS)

代码

def dfs(current, target, visited, path):visited[current] = Truepath.append(current)if current == target:return Truefor neighbor in graph[current]:if not visited[neighbor]:if dfs(neighbor, target, visited, path):return Truepath.pop()return False

功能

  • 使用递归实现深度优先搜索(DFS),从起点 current 开始,找到目标节点 target 的路径。

  • 参数说明:

    • current:当前访问的节点。

相关文章:

(蓝桥杯——10. 小郑做志愿者)洛斯里克城志愿者问题详解

题目背景 小郑是一名大学生,她决定通过做志愿者来增加自己的综合分。她的任务是帮助游客解决交通困难的问题。洛斯里克城是一个六朝古都,拥有 N 个区域和古老的地铁系统。地铁线路覆盖了树形结构上的某些路径,游客会询问两个区域是否可以通过某条地铁线路直达,以及有多少条…...

TypeScript跟js,es6这些的区别

TypeScript 一、TypeScript 是什么 想象 JavaScript 是一个自由奔放的艺术家,它在创作(编写代码)时不受太多约束,非常灵活,但有时也容易犯错且难以调试。而 TypeScript 就像是给这位艺术家配备了一套精确的工具和规范…...

flink-cdc同步数据到doris中

1 创建数据库和表 1.1 数据库脚本 这样直接创建数据库是有问题,因为后面发现superset连接使用doris://root:12345610.101.12.82:9030/internal.eayc?charsetutf8mb4 -- 创建数据库eayc create database if not exists ods_eayc; -- 创建数据表2 数据同步 2.1 f…...

Kubernetes:EKS 中 Istio Ingress Gateway 负载均衡器配置及常见问题解析

引言 在云原生时代,Kubernetes 已经成为容器编排的事实标准。AWS EKS (Elastic Kubernetes Service) 作为一项完全托管的 Kubernetes 服务,简化了在 AWS 上运行 Kubernetes 的复杂性。Istio 作为服务网格领域的佼佼者,为微服务提供了流量管理…...

Golang教程

1. go 环境与命令 1.1 go 环境搭建 SDK 安装 Go 官网:golang.orgGo 中文社区:https://studygolang.com/dlGo API文档:https/golang.org 或 https://studygolang.com/pkgdoc 目录 api :api 存放bin:go命令src&#…...

AI 百炼成神:线性回归,预测房价

我们开始第一个项目——线性回归:预测房价。这是一个经典的机器学习入门项目,可以帮助你理解如何使用线性回归模型来预测连续的数值。 第一个项目:线性回归预测房价 项目目标 学习线性回归的基本概念。使用历史房价数据建立一个预测模型。理解如何评估模型的性能。项目步骤…...

企业软件合规性管理:构建高效、安全的软件资产生态

引言 在数字化转型的浪潮下,企业的软件使用方式日益多元化,涉及云端、订阅制、永久授权及浮动许可等多种模式。然而,随着软件资产的增多,企业面临着合规性管理的严峻挑战:非法软件使用、许可证管理不当、软件资产闲置…...

每日一题——编辑距离

编辑距离 参考资料题目描述示例 解题思路动态规划(DP)方法 代码实现复杂度分析示例详解示例1:"nowcoder" → "new"示例2:"intention" → "execution" 总结与心得 参考资料 建议先参考下…...

TensorFlow项目GPU运行 安装步骤

以下是在 Linux 系统 下搭建完整 GPU 加速环境的详细流程(适配 CUDA 11.2 和 Python 3.9): 1. 前置检查 1.1 验证 NVIDIA 驱动 # 检查驱动版本(需 ≥ 450.80.02) nvidia-smi 输出示例: CUDA Version: 11.2…...

c++进阶———继承

1.引言 在一些大的项目中,我们可能要重复定义一些类,但是很麻烦,应该怎么办呢?举个简单的例子,我要做一个全校师生统计表,统计学号,教师编号,姓名,年龄,电话…...

FreeSwitch的mod_translate模块详细,附带场景案例及代码示例

mod_translate 模块详细介绍 mod_translate 是 FreeSWITCH 中的一个拨号计划应用程序模块,用于对电话号码或字符串进行格式转换和翻译。它可以根据预定义的规则对输入的内容进行匹配和转换,常用于号码格式化、路由选择、号码屏蔽等场景。 主要功能 号码…...

前端504错误分析

前端出现504错误(网关超时)通常是由于代理服务器未能及时从上游服务获取响应。以下是详细分析步骤和解决方案: 1. 确认错误来源 504含义:代理服务器(如Nginx、Apache)在等待后端服务响应时超时。常见架构:前端 → 代理服务器 → 后端服务,问题通常出在代理与后端之间。…...

在 .NET 8/9 中使用 AppUser 进行 JWT 令牌身份验证

文章目录 一、引言二、什么是 JSON Web 令牌?三、什么是 JSON Web 令牌结构?四、设置 JWT 令牌身份验证4.1 创建新的 .NET 8 Web API 项目4.2 安装所需的 NuGet 软件包4.3 创建 JWT 配置模型4.4 将 JWT 配置添加到您的 appsettings.json 中4.5 为 Config…...

基于python实现机器学习的心脏病预测系统

以下是一个基于 Python 实现的简单心脏病预测系统代码示例,我们将使用 Scikit - learn 库中的机器学习算法(这里以逻辑回归为例),并使用公开的心脏病数据集。 步骤: 数据加载与预处理:加载心脏病数据集&a…...

使用 NVM 随意切换 Node.js 版本

安装nvm https://github.com/coreybutler/nvm-windows/releases nvm安装详细教程(卸载旧的nodejs,安装nvm、node、npm、cnpm、yarn及环境变量配置)-CSDN博客 验证 NVM 是否安装成功-查看版本 nvm --version安装指定版本的 Node.js nvm i…...

【Prometheus】prometheus结合pushgateway实现脚本运行状态监控

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全…...

SpringBoot 项目配置动态数据源

目录 一、前言二、操作1、引入依赖2、配置默认数据库 13、定义数据源实体和 Repository4、定义动态数据源5、配置数据源6、定义切换数据源注解7、定义切面类8、使用注解切换数据源 一、前言 通过切面注解方式根据不同业务动态切换数据库 二、操作 1、引入依赖 <dependen…...

CSS基本选择器

1. 通配选择器 作用&#xff1a;可以选中所有的 HTML 元素。 语法&#xff1a; * { 属性名: 属性值; } 举例&#xff1a; <!DOCTYPE html> <html lang"zh-cn"> <head><meta charset"UTF-8"><meta name"viewport" …...

idea-代码补全快捷键

文章目录 前言idea-代码补全快捷键1. 基本补全2. 类型匹配补全3. 后缀补全4. 代码补全 前言 如果您觉得有用的话&#xff0c;记得给博主点个赞&#xff0c;评论&#xff0c;收藏一键三连啊&#xff0c;写作不易啊^ _ ^。   而且听说点赞的人每天的运气都不会太差&#xff0c;…...

基于SpringBoot+vue粮油商城小程序系统

粮油商城小程序为用户提供方便快捷的在线购物体验&#xff0c;包括大米、面粉、食用油、调味品等各种粮油产品的选购&#xff0c;用户可以浏览商品详情、对比价格、下单支付等操作。同时&#xff0c;商城还提供优惠活动、积分兑换等福利&#xff0c;让用户享受到更多实惠和便利…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...