当前位置: 首页 > 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;让用户享受到更多实惠和便利…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...