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

23.8.8 杭电暑期多校7部分题解

1008 - H.HEX-A-GONE Trails

题目大意

有两个玩家和一棵树,初始状态玩家一和玩家二分别在两个点 x , y x,\space y x, y,每次操作可以走一个与当前点有连边并且双方都没走到过的点,问最后是谁赢

解题思路

因为不能走走过的点,因此每个人走的路径一定是一条链

很明显当玩家一不选择往与玩家二所在的点的路径走,相当于把 x → y x\to y xy 的链让给了玩家二

因此如果想要这么走就应该保证对方此时能走的链没有比你要走的长

那么可以开个数组存储 x → y x\to y xy 路径上每个点只经过非路径上的点所能走的最长的链长,可以用树形dp解决

这样操作之后就将问题转化到了数组中解决

双方分别用set维护在当前点所能到达的最远的距离

如果当前玩家离开 x → y x\to y xy 的路径能到的最远的距离比对方set内的最大值大则必胜

如没有必胜策略则继续沿路径走并在双方set中删除不可达的方案

如果双方到见面了还没必胜则比较两者接下来能到的最远距离

具体细节参考代码,哥们觉得太抽象了不好将

code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
struct lol {int x, y;} e[N << 1];
int t, n, a, b, ans, top[N], vis[N], dep[2][N], f[2][N], p[N], fl;
multiset <int> s[2];
void ein(int x, int y) {e[++ ans].x = top[x];e[ans].y = y;top[x] = ans;
}
void dfs(int x, int fa, int op) {vis[x] ^= 1; f[op][x] = fa; dep[op][x] = dep[op][fa] + 1;if ((x == a || x == b) && fa != 0) return;for (int i = top[x]; i; i = e[i].x) {int y = e[i].y;if (y == fa) continue;dfs(y, x, op);}
}
void dfs1(int x, int fa, int rt) {p[rt] = max(p[rt], max(dep[0][x] - dep[0][rt], dep[1][x] - dep[1][rt]) + 1);for (int i = top[x]; i; i = e[i].x) {int y = e[i].y;if (vis[y] == 2 || y == fa) continue;dfs1(y, x, rt);}
}
int main() {scanf("%d", &t);while (t --) {scanf("%d%d%d", &n, &a, &b); ans = fl = 0;s[0].clear(); s[1].clear();for (int i = 1; i <= n; ++ i)top[i] = p[i] = vis[i] = dep[0][i] = dep[1][i] = 0;for (int i = 1, u, v; i < n; ++ i)scanf("%d%d", &u, &v), ein(u, v), ein(v, u);dfs(a, 0, 0);dfs(b, 0, 1);for (int x = b; x; x = f[0][x]) vis[x] = 2;for (int x = b; x; x = f[0][x]) {dfs1(x, 0, x);if (x != b) s[0].insert(p[x] + dep[0][x] - 1);if (x != a) s[1].insert(p[x] + dep[1][x] - 1);}int x1 = a, x2 = b, i;for (i = 0; x1 != f[0][x2]; ++ i)if ((i & 1) == 0) {if (p[x1] > *prev(s[1].end()) - i / 2) {fl = 1; break;}auto it = s[0].find(p[x1] + i / 2); s[0].erase(it);x1 = f[1][x1];it = s[1].find(p[x1] + dep[1][x1] - 1); s[1].erase(it);} else {if (p[x2] > *prev(s[0].end()) - (i + 1) / 2) {fl = 1; break;}auto it = s[1].find(p[x2] + i / 2); s[1].erase(it);x2 = f[0][x2];it = s[0].find(p[x2] + dep[0][x2] - 1); s[0].erase(it);}if (fl) printf("%d\n", (i & 1) ^ 1);else if ((i & 1) == 1) printf("%d\n", p[x2] > p[x1] ? 0 : 1);else printf("%d\n", p[x1] > p[x2] ? 1 : 0);}return 0;
}

相关文章:

23.8.8 杭电暑期多校7部分题解

1008 - H.HEX-A-GONE Trails 题目大意 有两个玩家和一棵树&#xff0c;初始状态玩家一和玩家二分别在两个点 x , y x,\space y x, y&#xff0c;每次操作可以走一个与当前点有连边并且双方都没走到过的点&#xff0c;问最后是谁赢 解题思路 因为不能走走过的点&#xff0c…...

《24海南大学835软件工程考研经验贴》

1.经验之谈 首先&#xff0c;我是一个二战的考生&#xff0c;一战给我带来的经验有几点。第一&#xff0c;数学、专业课这两门越早复习越好&#xff0c;越拖到后面你就会发现来不及了&#xff0c;这学不完&#xff0c;那学不完的。第二、我认为是比较关键的一点&#xff0c;一定…...

【yolo系列:运行报错AttributeError: module ‘torch.nn‘ has no attribute ‘Mish‘】

最近运行yolov7报错AttributeError: module ‘torch.nn‘ has no attribute ‘Mish‘ 网上搜罗了一系列的报错方法但是都不怎么好解决&#xff0c;那么在这里给出具体解决方法&#xff0c;以及一些别人的参考文章。 这里先解释自己的&#xff0c;然后再给出别人的相对应的报错…...

Leetcode 剑指 Offer II 039. 直方图最大矩形面积

题目难度: 困难 原题链接 今天继续更新 Leetcode 的剑指 Offer&#xff08;专项突击版&#xff09;系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述 给定非负整数数组 heights &#xff0c;数组中的数字用来表示柱状…...

SpringBoot案例-部门管理-修改

目录 前言 查看页面原型&#xff0c;明确需求 页面原型 需求 阅读接口文件 思路分析 功能接口开发 控制层&#xff08;Controller类&#xff09; 业务层&#xff08;Service类&#xff09; 业务类 业务实现类 持久层&#xff08;Mapper类&#xff09; 接口测试 前…...

element-ui表格数据为空,图片占位提示

当表格的绑定数据为空时常需要显示暂无数据等字样&#xff0c;这时候就用到了empty-text <el-table:data"tableData"stripeborderempty-text"暂无数据"> 但&#xff0c;当数据为空&#xff0c;想用图片展示呢&#xff0c;如下图 方法一&#xff1a…...

C++ STL vector 模拟实现

✅<1>主页&#xff1a;我的代码爱吃辣 &#x1f4c3;<2>知识讲解&#xff1a;C之STL &#x1f525;<3>创作者&#xff1a;我的代码爱吃辣 ☂️<4>开发环境&#xff1a;Visual Studio 2022 &#x1f4ac;<5>前言&#xff1a;上次我们已经数字会用…...

51单片机学习--红外遥控(外部中断)

需要利用下面这个红外接收头&#xff0c;OUT口会发出红外信号对应的高低电平&#xff0c;由于发送的速度很快&#xff0c;所以需要把OUT引脚接在外部中断引脚上&#xff0c;当OUT一旦产生下降沿&#xff0c;马上进中断&#xff0c;这样响应会更及时。 外部中断引脚位于P3_2和P…...

后端开发10.规格模块

概述 简介 效果图...

腾讯出了一个新聊天软件M8

众所周知&#xff0c;如今国内互联网&#xff0c;微信和QQ无疑是社交领域的霸主。 下载:https://www.123pan.com/s/BP5A-RW4xh.html 不过&#xff0c;它们也有各自局限性&#xff0c;比如难以结识新朋友、功能过于复杂等。 这让用户产生厌倦&#xff0c;再加上近几年AI、元宇…...

C++ QT(一)

目录 初识QtQt 是什么Qt 能做什么Qt/C与QML 如何选择Qt 版本Windows 下安装QtLinux 下安装Qt安装Qt配置Qt Creator 输入中文配置Ubuntu 中文环境配置中文输入法 Qt Creator 简单使用Qt Creator 界面组成Qt Creator 设置 第一个Qt 程序新建一个项目项目文件介绍项目文件*.pro样式…...

微信小程序时钟

微信小程序自定义时钟&#xff0c;模拟翻牌时钟。1、页面布局 <view class"date-time-box"><view class"date-box">{{nowDate}}</view><view class"time-box"><view><image class"pic01 {{move[0]?move…...

HttpRunner自动化工具之设置代理和请求证书验证

httprunner设置代理&#xff1a; httprunner 库本身没有提供设置代理的接口&#xff0c;但是底层使用了urllib.requests 等库&#xff0c;可以设置HTTP_PROXY 和HTTPS_PROXY 环境变量&#xff0c;常用的网络库会自动识别这些环境变量。 日常调试使用代理&#xff08;如charles…...

opsForHash() 与 opsForValue 请问有什么区别?

&#x1f449;&#xff1a;&#x1f517;官方API参考手册 如图&#xff0c;opsForHash()返回HashOperations<K,HK,HV>但是 opsForValue()返回ValueOperations<K,V>… 区别就是opsForHash的返回值泛型中有K,HK,HV,其中K是Redis指定的某个数据库里面某一个关键字(由…...

具有吸引子的非线性系统(MatlabSimulink实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

Linux一些常见的命令

1. 基础命令 1. ls&#xff1a; 列出目录内容。- 例如&#xff1a;ls -l 以长格式列出文件和目录。2. cd&#xff1a; 切换工作目录。- 例如&#xff1a;cd /home/user 进入 /home/user 目录。3. pwd&#xff1a; 显示当前工作目录的路径。4. mkdir&#xff1a; 创建新目录。-…...

正则表达式的基本知识

正则表达式是一种用于匹配和操作字符串的强大工具。它是由一系列字符和特殊符号组成的模式&#xff0c;可以用来检查字符串是否符合某种模式&#xff0c;进行匹配、替换、提取等操作。 下面是一些常见的正则表达式元字符和语法&#xff1a; 1. 字符匹配&#xff1a; - 普通…...

如何⽤webpack 来优化前端性能

如何⽤webpack 来优化前端性能&#xff1f; ⽤webpack 优化前端性能是指优化 webpack 的输出结果&#xff0c;让打包的最终结果在浏览器运⾏快速⾼效。 压缩代码&#xff1a;删除多余的代码、注释、简化代码的写法等等⽅式。可以利⽤webpack的 UglifyJsPlugin 和 ParallelUgl…...

人机交互中的混合多重反馈

人机交互中态、势、感、知的混合多重反馈是指在交互过程中综合运用不同方面的反馈信息&#xff0c;包括用户态度&#xff08;态&#xff09;、行为动势&#xff08;势&#xff09;、情感体验&#xff08;感&#xff09;和认知反馈&#xff08;知&#xff09;。这种多重反馈可以…...

CSS:服务器字体 与 响应式布局(用法 + 例子 + 效果)

文章目录 服务器字体定义 服务器字体使用例子 响应式布局设备类型设备特性例子 服务器字体 解决字体不一致而产生的。 首先&#xff0c;在网上把字体下载好。 定义 服务器字体 font-face{font-family:字体名称;src:url(字体资源路径); }使用 在需要使用的选择器里加上 font…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

【堆垛策略】设计方法

堆垛策略的设计是积木堆叠系统的核心&#xff0c;直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法&#xff0c;涵盖基础规则、优化算法和容错机制&#xff1a; 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则&#xff1a; 大尺寸/重量积木在下&#xf…...

算术操作符与类型转换:从基础到精通

目录 前言&#xff1a;从基础到实践——探索运算符与类型转换的奥秘 算术操作符超级详解 算术操作符&#xff1a;、-、*、/、% 赋值操作符&#xff1a;和复合赋值 单⽬操作符&#xff1a;、--、、- 前言&#xff1a;从基础到实践——探索运算符与类型转换的奥秘 在先前的文…...

向量几何的二元性:叉乘模长与内积投影的深层联系

在数学与物理的空间世界中&#xff0c;向量运算构成了理解几何结构的基石。叉乘&#xff08;外积&#xff09;与点积&#xff08;内积&#xff09;作为向量代数的两大支柱&#xff0c;表面上呈现出截然不同的几何意义与代数形式&#xff0c;却在深层次上揭示了向量间相互作用的…...