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

洛谷 P10289 [GESP样题 八级] 小杨的旅游 C++ 完整题解

一、题目链接

P10289 [GESP样题 八级] 小杨的旅游 - 洛谷

二、题目大意

n个节点之间有n - 1条边,其中k个节点是传送门,任意两个传送门之间可以 以0单位地时间相互到达。问从u到v至少需要多少时间?

三、解题思路

输入不必多讲。

cin >> n >> k >> q;
for (int i = 1; i <= n - 1; i++) {int x, y;cin >> x >> y;e[x].push_back(y);e[y].push_back(x);
}
for (int i = 1; i <= k; i++) cin >> door[i];

BFS?DFS?

对于这个题目,你肯定会想到用DFS和BFS直接去做。

或者

当然了,更好的方法一定还有,本文只是介绍了一种方法。

正解

分成两种方案:使用传送门和不使用传送门,取快者。

使用传送门

用BFS找到每个节点离最近传送点的距离存入dst数组,结果就是:从起点走到最近传送点 -> 传送到离终点最近的传送点 -> 走到终点 dst[u] + dst[v]

int dst[N]; // dst[i] = i 到 离i最近的传送点 的距离void bfs() {memset(dst, 0x3f, sizeof (dst));queue<int> qu;for (int i = 1; i <= k; i++) {qu.push(door[i]); // 存入所有的传送点dst[door[i]] = 0;}while (!qu.empty()) {int now = qu.front();qu.pop();for (int x : e[now]) {if (dst[x] == 0x3f3f3f3f) {dst[x] = dst[now] + 1; // 更新x离最近传送点的位置qu.push(x);}}}
}
...
{
...bfs();int res1 = dst[u] + dst[v];
...
}
...

不使用传送门

普通的BFS方法超时了,这里介绍一种可行的方法(LCA)

什么是LCA

LCA的意思是最近公共祖先,如下图,A与B的最近公共祖先是X。

如何用LCA计算A到B的距离
距离dist

首先计算每个节点离根的距离,也就是深度 - 1。

A与B的距离

= dist[A] + dist[B] - 2 * dist[x]

建立dist

int dist[N] = {-1}; // dist[0] = -1 dist[1]才能 = 0
void dfs(int fa, int x) {dist[x] = dist[fa] + 1;for (int u : e[x]) {if (u != fa) // 不能走回头路 省去vis数组dfs(x, u);}
}
...
{
...dfs(0, 1); // 起初给一个无意义的0作为根节点的父亲
...
}
...

接着是lca函数:

int lca(int u, int v);

lca函数中有两个工作要做

1. 把u和v的深度化作一样 循环上移u或者v,直到dist[u] == dist[v]

// 半伪代码
if (dist[u] > dist[v])swap(u, v); // 保证v更深 要不停更新v
while (dist[u] < dist[v]) {v = v的父亲;
}
if (u == v) // 如果在没有更新 u 的情况下两者相等 那已经找到了最近公共祖先return u;

2. u和v一起更新 直到两者相等就返回

// 半伪代码
while (u != v) {u = u的父亲;v = v的父亲;
}
return u;

太慢了!!!

u 或者 v一层一层上去可没时间。

极端情况下就是这样:

每次处理数据都需要进行一次,假设q = 数据最大值,循环次数就是(2 * 100000) ^ 2 = 40,000,000,000。

使用倍增法优化

我们把u,v的第x个祖先看成2 ^ x + 2 ^ y + 2 ^ z...

int f[N][20]; // f[x][i] 节点 x 的 第2^i 个祖先(从下往上)

DFS中记录下任意节点的第2 ^ i个祖先,如下(包含原本的代码)。

void dfs(int fa, int x) {dist[x] = dist[fa] + 1;f[x][0] = fa; // x的第2^0(1)个祖先就是它爹for (int i = 1; i <= 18; i++)f[x][i] = f[f[x][i - 1]][i - 1]; // x的第2^i个祖先就是 它2^(i-1)个祖先的第2^(i-1)个祖先 因为2^i = 2^(i-1) + 2^(i-1)for (int u : e[x]) {if (u != fa)dfs(x, u);}
}

LCA中也要改动。

int lca(int u, int v) {// 1if (dist[u] > dist[v])swap(u, v);for (int i = 18; i >= 0; i--) { // 2^18 > 2*10^5if (dist[u] <= dist[f[v][i]])v = f[v][i];if (u == v) return u;}//2for (int i = 18; i >= 0; i--) {if (f[u][i] != f[v][i])u = f[u][i], v = f[v][i];}return f[u][0]; // u和v最后是它们公共祖先的两个儿子 所以它们公共祖先是它们任意一个的父亲
}

块1:i从18开始,试探v的第2^i个祖先 是否 存在 并 深度大于等于u,如果满足以上条件就把v变成v的第2^i个祖先,然后i = 17,16...继续试探,直到u == v或i == 0。

块2:i同样从18开始,试探v的第2^i个祖先 是否和 u的第2^i个祖先不相等,如果不相等,就更新u和v(同上),循环结束后,u和v一定是它们最近公共祖先的两个儿子,最后返回它们任意一个的父亲。

四、完整代码

长度有点小小的震撼,但相信你已经看懂了。

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;const int N = 200005;vector<int> e[N];
int n, k, q, door[N]; // door[] 存放每个传送点
int dist[N] = {-1}, f[N][20]; // dist[] 每个点离根节点的距离 f[x][i] 节点 x 的 第2^i 个祖先(从下往上)
int dst[N]; // dst[i] = i 到 离i最近的传送点 的距离void bfs() {memset(dst, 0x3f, sizeof (dst));queue<int> qu;for (int i = 1; i <= k; i++) {qu.push(door[i]); // 存入所有的传送点dst[door[i]] = 0;}while (!qu.empty()) {int now = qu.front();qu.pop();for (int x : e[now]) {if (dst[x] == 0x3f3f3f3f) {dst[x] = dst[now] + 1; // 更新x离最近传送点的位置qu.push(x);}}}
}void dfs(int fa, int x) {dist[x] = dist[fa] + 1;f[x][0] = fa;for (int i = 1; i <= 18; i++)f[x][i] = f[f[x][i - 1]][i - 1];for (int u : e[x]) {if (u != fa)dfs(x, u);}
}int lca(int u, int v) {if (dist[u] > dist[v])swap(u, v);for (int i = 18; i >= 0; i--) {if (dist[u] <= dist[f[v][i]])v = f[v][i];if (u == v) return u;}for (int i = 18; i >= 0; i--) {if (f[u][i] != f[v][i])u = f[u][i], v = f[v][i];}return f[u][0];
}int solve(int u, int v) {// ** 使用传送门int res1 = dst[u] + dst[v]; // 找离起点最近的传送点 传送至 离终点最近的传送点// **不使用传送门int res2 = dist[u] + dist[v] - 2 * dist[lca(u, v)];return min(res1, res2); // 取小者
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> k >> q;for (int i = 1; i <= n - 1; i++) {int x, y;cin >> x >> y;e[x].push_back(y);e[y].push_back(x);}for (int i = 1; i <= k; i++) cin >> door[i];bfs();dfs(0, 1);while (q--) {int u, v;cin >> u >> v;cout << solve(u, v) << endl;}return 0;
}

相关文章:

洛谷 P10289 [GESP样题 八级] 小杨的旅游 C++ 完整题解

一、题目链接 P10289 [GESP样题 八级] 小杨的旅游 - 洛谷 二、题目大意 n个节点之间有n - 1条边&#xff0c;其中k个节点是传送门&#xff0c;任意两个传送门之间可以 以0单位地时间相互到达。问从u到v至少需要多少时间&#xff1f; 三、解题思路 输入不必多讲。 cin >> …...

使用 Tauri 2 + Next.js 开发跨平台桌面应用实践:Singbox GUI 实践

Singbox GUI 实践 最近用 Tauri Next.js 做了个项目 - Singbox GUI&#xff0c;是个给 sing-box 用的图形界面工具。支持 Windows、Linux 和 macOS。作为第一次接触这两个框架的新手&#xff0c;感觉收获还蛮多的&#xff0c;今天来分享下开发过程中的一些经验~ 为啥要做这个…...

JWT入门

一、初识JWT&#xff1a;新时代的身份认证方案 在分布式系统成为主流的今天&#xff0c;传统的Session认证方式逐渐显露出局限性。JWT&#xff08;JSON Web Token&#xff09;作为现代Web开发的认证新标准&#xff0c;凭借其无状态、跨域友好和安全性等特性&#xff0c;正在成为…...

Python - Quantstats量化投资策略绩效统计包 - 详解

使用Quantstats包做量化投资绩效统计的时候因为Pandas、Quantstats版本不匹配踩了一些坑&#xff1b;另外&#xff0c;Quantstats中的绩效统计指标非常全面&#xff0c;因此详细记录一下BUG修复方法、使用说明以及部分指标的内涵示意。 一、Quantstats安装及版本匹配问题 可以…...

智慧园区管理系统推动企业智能运维与资源优化的全新路径分析

内容概要 在当今快速发展的商业环境中&#xff0c;园区管理的数字化转型显得尤为重要。在这个背景下&#xff0c;快鲸智慧园区管理系统应运而生&#xff0c;成为企业实现高效管理的最佳选择。它通过整合互联网、物联网等先进技术&#xff0c;以智能化的方式解决了传统管理模式…...

【数据结构-字典树】力扣14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀&#xff0c;返回空字符串 “”。 示例 1&#xff1a; 输入&#xff1a;strs [“flower”,“flow”,“flight”] 输出&#xff1a;“fl” 示例 2&#xff1a; 输入&#xff1a;strs [“dog”,“racecar…...

《深入浅出HTTPS​​​​​​​​​​​​​​​​​》读书笔记(31):HTTPS和TLS/SSL

《深入浅出HTTPS​​​​​​​​​​》读书笔记&#xff08;31&#xff09;&#xff1a;HTTPS和TLS/SSL TLS/SSL协议和应用层协议无关&#xff0c;它只是加密应用层协议&#xff08;比如HTTP&#xff09;并传递给下层的TCP。 HTTP和TLS/SSL协议组合在一起就是HTTPS, HTTPS等…...

Go学习:Go语言中if、switch、for语句与其他编程语言中相应语句的格式区别

Go语言中的流程控制语句逻辑结构与其他编程语言类似&#xff0c;格式有些不同。Go语言的流程控制中&#xff0c;包括if、switch、for、range、goto等语句&#xff0c;没有while循环。 目录 1. if 语句 2. switch语句 3. for语句 4. range语句 5. goto语句&#xff08;不常用…...

L30.【LeetCode笔记】设计链表

1.题目 707. 设计链表 - 力扣&#xff08;LeetCode&#xff09; 你可以选择使用单链表或者双链表&#xff0c;设计并实现自己的链表。 单链表中的节点应该具备两个属性&#xff1a;val 和 next 。val 是当前节点的值&#xff0c;next 是指向下一个节点的指针/引用。 如果是双向…...

java日志框架详解-Log4j2

一、概述 Apache Log4j 2 &#xff08;Log4j – Apache Log4j 2&#xff09;是对Log4j的升级&#xff0c;它比其前身Log4j 1.x提供了重大改进&#xff0c;并参考了Logback中优秀的设计&#xff0c;同时修复了Logback架构中的一些问题。被誉为是目前最优秀的Java日志框架&#x…...

C++中vector追加vector

在C中&#xff0c;如果你想将一个vector追加到另一个vector的后面&#xff0c;可以使用std::vector的成员函数insert或者std::copy&#xff0c;或者简单地使用std::vector的push_back方法逐个元素添加。这里我将展示几种常用的方法&#xff1a; 方法1&#xff1a;使用insert方…...

加一(66)

66. 加一 - 力扣&#xff08;LeetCode&#xff09; 解法&#xff1a; class Solution { public:vector<int> plusOne(vector<int>& digits) {bool plus_one true;for (int i digits.size() - 1; i > 0; --i) {if (plus_one) {int tmp digits[i] 1;if …...

远程连接-简化登录

vscode通过ssh连接远程服务器免密登录&#xff08;图文&#xff09;_vscode ssh-CSDN博客...

canvas的基本用法

canvas canvas元素简介 1.是个container元素<canvas width100 height100></canvas>&#xff0c;有开闭标签 2.有且只有width和height两个attribute&#xff0c;不需要写单位 canvas的基本使用 const canvasEl document.getElementById(canvas01) const ctx …...

Tailwind CSS - Tailwind CSS 引入(安装、初始化、配置、引入、构建、使用 Tailwind CSS)

一、Tailwind CSS 概述 Tailwind CSS 是一个功能优先的 CSS 框架&#xff0c;它提供了大量的实用类&#xff08;utility classes&#xff09;&#xff0c;允许开发者通过组合这些类来快速构建用户界面 Tailwind CSS 与传统的 CSS 框架不同&#xff08;例如&#xff0c;Bootstr…...

鸿蒙开发黑科技“stack叠层”替代customdialog

前一篇提到的问题,本篇博文提出了一个解决方案: arkui-x LongPressGesture触发customdialog踩坑记录-CSDN博客 前一段时间遇到的这个问题,通过排除法观察,锁定为customdialog组件有bug,极为容易挂死。不论如何调整使用方法,都还是会触发挂死。 反馈给arkui团队,说是在…...

FreeRTOS从入门到精通 第十五章(事件标志组)

参考教程&#xff1a;【正点原子】手把手教你学FreeRTOS实时系统_哔哩哔哩_bilibili 一、事件标志组简介 1、概述 &#xff08;1&#xff09;事件标志位是一个“位”&#xff0c;用来表示事件是否发生。 &#xff08;2&#xff09;事件标志组是一组事件标志位的集合&#x…...

智慧园区管理平台实现智能整合提升企业运营模式与管理效率

内容概要 在当今数字化的背景下&#xff0c;智慧园区管理平台正逐渐成为企业提升运营效率和管理模式的重要工具。这个平台汇聚了多种先进技术&#xff0c;旨在通过智能整合各类资源与信息&#xff0c;帮助企业实现全面的管理创新。 智慧园区管理平台不仅仅是一个数据处理工具…...

markdown公式特殊字符

个人学习笔记 根号 在 Markdown 中&#xff0c;要表示根号 3&#xff0c;可以使用 LaTeX 语法来实现。常见的有以下两种方式&#xff1a; 行内公式形式&#xff1a;使用一对美元符号 $ 将内容包裹起来&#xff0c;即 $\sqrt{3}$ &#xff0c;在支持 LaTeX 语法渲染的 Markdow…...

【深度分析】微软全球裁员计划不影响印度地区,将继续增加当地就业机会

当微软的裁员刀锋掠过全球办公室时&#xff0c;班加罗尔的键盘声却愈发密集——这场资本迁徙背后&#xff0c;藏着数字殖民时代最锋利的生存法则。 表面是跨国公司的区域战略调整&#xff0c;实则是全球人才市场的地壳运动。微软一边在硅谷裁撤年薪20万美金的高级工程师&#x…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...