当前位置: 首页 > 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…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

加密通信 + 行为分析:运营商行业安全防御体系重构

在数字经济蓬勃发展的时代&#xff0c;运营商作为信息通信网络的核心枢纽&#xff0c;承载着海量用户数据与关键业务传输&#xff0c;其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级&#xff0c;传统安全防护体系逐渐暴露出局限性&a…...

Mac flutter环境搭建

一、下载flutter sdk 制作 Android 应用 | Flutter 中文文档 - Flutter 中文开发者网站 - Flutter 1、查看mac电脑处理器选择sdk 2、解压 unzip ~/Downloads/flutter_macos_arm64_3.32.2-stable.zip \ -d ~/development/ 3、添加环境变量 命令行打开配置环境变量文件 ope…...

职坐标物联网全栈开发全流程解析

物联网全栈开发涵盖从物理设备到上层应用的完整技术链路&#xff0c;其核心流程可归纳为四大模块&#xff1a;感知层数据采集、网络层协议交互、平台层资源管理及应用层功能实现。每个模块的技术选型与实现方式直接影响系统性能与扩展性&#xff0c;例如传感器选型需平衡精度与…...

GB/T 43887-2024 核级柔性石墨板材检测

核级柔性石墨板材是指以可膨胀石墨为原料、未经改性和增强、用于核工业的核级柔性石墨板材。 GB/T 43887-2024核级柔性石墨板材检测检测指标&#xff1a; 测试项目 测试标准 外观 GB/T 43887 尺寸偏差 GB/T 43887 化学成分 GB/T 43887 密度偏差 GB/T 43887 拉伸强度…...