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

pkucpc2025 L:Game on Tree

news 来源：原创 2025/7/25 14:03:13

题意

两个人在一棵无根树上玩游戏，每次可以删掉若干个叶子节点，不能操作的人输。

思路

比赛的时候我去写H Quintuple了，队友貌似在我写的时候把这道题讨论出来了。
后来补题的时候花了大概花了70分钟左右ac这道题。

首先考虑一条链的情况，那么必败态是链的长度为3的倍数，十分显然。

就是这个结论误导了我很久。

后面发现了一个很有趣的性质，如果存在一个叶子节点，把它删掉以后不会产生新的叶子节点，那么必胜：考虑去掉这个叶子节点以后的树，如果是必败的，那么只需要去掉这个叶子节点；否则去掉这个叶子节点并且并将剩下的部分转移成必败态。

然后就变成了判断是否有叶子节点到一个deg>=3的点的距离为奇数，如果有就是必胜。

#include <bits/stdc++.h>
#define ll long long
using namespace std;const int N = 1e3 + 10;int n; vector<int> e[N];void solve() {cin >> n;for (int i = 1; i <= n; i++) {e[i].clear();}for (int i = 1; i < n; i++) {int x, y;cin >> x >> y;e[x].push_back(y);e[y].push_back(x);}int mx = 0;for (int i = 1; i <= n; i++) {mx = max(mx, (int)e[i].size());}if (mx <= 2) {cout << ((n - 1) % 3 ? "Alice\n" : "Bob\n");return;}for (int i = 1; i <= n; i++) {if (e[i].size() > 1) continue;int x = i; int last = 0;int cnt = 0;while (e[x].size() <= 2) {int nxt;for (int y : e[x]) {if (y == last) continue;nxt = y; break;}last = x, x = nxt, cnt++;}if (cnt & 1) {cout << "Alice\n";return;}}cout << "Bob\n";
}int main() {// freopen("in.in", "r", stdin);ios::sync_with_stdio(false);cin.tie(nullptr);int T; cin >> T;while (T--) {solve();}
}

相关文章：

pkucpc2025 L:Game on Tree

题意 两个人在一棵无根树上玩游戏&#xff0c;每次可以删掉若干个叶子节点&#xff0c;不能操作的人输。 思路 比赛的时候我去写H Quintuple了&#xff0c;队友貌似在我写的时候把这道题讨论出来了。 后来补题的时候花了大概花了70分钟左右ac这道题。 首先考虑一条链的情况…...

编程日记 2025/7/25 14:03:13

大数据实时分析：ClickHouse、Doris、TiDB 对比分析

随着企业对数据分析实时性、复杂性和多样性的要求越来越高，传统的批处理数仓已经无法满足实时指标看板、流量监控、用户行为分析等场景需求。因此，越来越多的公司开始引入实时分析型数据库系统。 目前，国内外常见的实时分析数据库有： ClickHouse：列式数据库，极致的分析性…...

编程日记 2025/7/24 13:27:11

网络流量分析系统的十大应用场景

在现代企业和组织的IT运维体系中&#xff0c;网络流量分析系统&#xff08;Network Traffic Analysis, NTA&#xff09;早已不仅仅是用来查看带宽使用率的“流量计数器”。随着网络环境的复杂化、攻击技术的不断演进&#xff0c;以及对业务连续性要求的提升&#xff0c;网络流量…...

编程日记 2025/7/23 15:28:51

问题 ｜ 代码审查：函数是否包含返回语句

“函数是否包含返回语句”这一问题的核心是&#xff1a;在编程中&#xff0c;函数是否按照设计要求正确使用了 返回语句&#xff08;如 return、return value&#xff09;&#xff0c;以便向调用者传递结果或控制权。以下是详细解释&#xff1a; 1. 什么是函数的返回语句&#…...

编程日记 2025/7/26 8:37:02

Spring Bean 生命周期中设计模式的应用与解析

Spring Bean 生命周期中使用的设计模式 Spring Bean 的生命周期涉及多个阶段和扩展点&#xff0c;Spring 框架在这一过程中巧妙运用了多种设计模式&#xff0c;以实现强大的功能和灵活性。以下是主要设计模式及其应用场景&#xff1a; 1. 工厂模式&#xff08;Factory Patter…...

编程日记 2025/7/24 22:25:18

设计模式的原理及深入解析

创建型模式 创建型模式主要关注对象的创建过程&#xff0c;旨在通过不同的方式创建对象&#xff0c;以满足不同的需求。 工厂方法模式 定义&#xff1a;定义一个创建对象的接口&#xff0c;让子类决定实例化哪一个类。 解释&#xff1a;工厂方法模式通过定义一个创建对象的…...

编程日记 2025/7/25 1:30:37

kotlin flow的两种SharingStarted策略的区别

一 两种 SharingStarted 策略的区别&#xff1a; SharingStarted.Eagerly: 立即开始收集上游流&#xff0c;即使没有下游订阅者持续保持活跃状态&#xff0c;直到 ViewModel 被清除优点&#xff1a;响应更快&#xff0c;数据始终保持最新缺点&#xff1a;消耗更多资源&#x…...

编程日记 2025/7/26 6:02:33

BGP综合实验（2）

一、实验需求 1、实验拓扑图 2、实验需求 使用 PreVal 策略&#xff0c;让 R4 经 R2 到达 192.168.10.0/24 。 使用 AS_Path 策略&#xff0c;让 R4 经 R3 到达 192.168.11.0/24 。 配置 MED 策略&#xff0c;让 R4 经 R3 到达 192.168.12.0/24 。 使用 Local Preference 策…...

编程日记 2025/7/21 7:19:46

python使用jsonpath-ng库操作json数据

jsonpath-ng 库的详细使用如下&#xff1a; 一、安装与导入 安装 通过 pip 安装库&#xff1a; pip install jsonpath-ng支持 Python 3.6 及以上版本。 导入核心模块 主要使用 parse 函数和 JSONPath 对象&#xff1a; from jsonpath_ng import parse二、基础查询操作 1. 简单…...

编程日记 2025/7/26 7:45:20

通用简洁工作汇报项目评估营销策划工作总结年终汇报PPT模版8套一组分享

工作总结汇报PPT模版8套一组分享&#xff1a;工作总结汇报PPT模版分享https://pan.quark.cn/s/04b7ab7a47c4 第一套PPT模版&#xff0c;主要是黄色和灰色调&#xff0c;上方有大面积黄色不规则形状背景&#xff0c;有“POWERPOINT”和“XXXXPPT模版”字样&#xff0c;左侧是黑…...

编程日记 2025/7/22 11:08:17

掌握Git：版本控制与高效协作指南

一、初始Git 提出问题&#xff1a;无论是在工作还是学习&#xff0c;我们在编写各种文档的时候&#xff0c;更改失误&#xff0c;失误后恢复到原来版本&#xff0c;不得不复制出一个副本。 每个版本由各自的内容&#xff0c;但最终只有一个报告需要被我们使用。 但在此之前的…...

编程日记 2025/7/25 17:33:00

ubuntu下配置vscode生成c_cpp_properties.json

-------------学习记录--------------- 在ubuntu下使用vscode时发现cpp文件无法读到头文件&#xff0c;明明头文件在合适的路径下&#xff0c;由于没有制定头文件的路径造成的这个问题。用这篇文章进行简单记录解决方法 ctrlshiftp打开命令面板&#xff0c;也可以点击左上角, …...

编程日记 2025/7/24 21:15:10

Qt读取Excel文件的技术实现与最佳实践

目录 一、成果展示二、核心方法及原理1. QAxObject&#xff08;基于COM接口&#xff09;2. 第三方库QXlsx3. ODBC数据库驱动 三、实现步骤详解1. QAxObject读取Excel&#xff08;需安装Excel/WPS&#xff09;2. QXlsx读取Excel&#xff08;跨平台方案&#xff09; 四、技术选型…...

编程日记 2025/7/22 2:16:41

双条件拆分工作表，一键生成独立工作簿-Excel易用宝

你是否遇到过这样的崩溃瞬间&#xff1f;面对一张密密麻麻的销售数据表&#xff0c;需要按指定维度拆分成工作簿和工作表&#xff0c;而你却只能手动复制粘贴到不同工作簿、工作表&#xff0c;改一个字段就花半小时&#xff0c;数据量大时甚至要熬夜加班&#xff1f; 别担心&a…...

编程日记 2025/7/23 18:36:16

iOS 蓝牙开发中的 BT 与 BLE

在 iOS 开发者的语境里，大家把 BT 和 BLE 当成两种不同的蓝牙技术在谈——它们来自同一个 Bluetooth 规范，但面向的场景、协议栈乃至 Apple 提供的 API 都截然不同。 缩写全称 / 技术名称规范层叫法iOS 支持现状典型用途BTBluetooth Classic（经典蓝牙）又叫 BR/EDR（Basic R…...

编程日记 2025/7/20 19:59:35

TCP和套接字SSL加密连接行为分析

目录 一、前言 二、背景 三、参数介绍 3.1、 have_openssl 3.2、have_ssl 3.3、require_secure_transport 四、--ssl-modemode 五、CREATE USER SSL/TLS选项 六、问题验证 6.1、使用套接字连接 6.2、使用TCP连接 七、分析与总结 一、前言 SSL&#xff08;Secure S…...

编程日记 2025/7/25 7:47:02

kafka 问与答

kafka Q&A How does the client connect to kafka and discovery the brokers. client 只需要知道一部分nodes(brokers)的地址既可以&#xff0c;client 会自动发现剩下的所有topic partition leader nodes, 然后连接上。 When a client connects:It uses the bootstrap…...

编程日记 2025/7/20 20:46:16

docker默认存储迁移

在容器化场景下默认存储路径为&#xff08;/var/lib/docker&#xff09;大多数平台根目录不支持系统盘扩容&#xff0c;会有空间不足风险隐患&#xff0c;因未配置持久化存储导致容器数据丢失。以迁移Docker存储路径至大容量/data目录说明 一、停止容器 systemctl stop docke…...

编程日记 2025/7/26 4:40:07

Ubuntu20.04系统下使用交叉编译工具链（aarch、x86）交叉编译opencv4.5.0

文章目录 0. 引言1. 准备交叉编译工具链2. 安装依赖工具3. 下载 OpenCV 源码4. 创建交叉编译工具链文件5. 配置 CMake 构建6. 构建 OpenCV7. 安装 OpenCV8. 验证9. 问题及解决办法 0. 引言 Ubuntu20.04系统下使用交叉编译工具链&#xff08;aarch、x86&#xff09;交叉编译ope…...

编程日记 2025/7/23 12:12:29

R语言数据可视化

R note book 文档–输出html格式文档&#xff0c;plotly不能生成PDF文件 --- title: "R语言数据可视化" output: html_notebook ---在R语言中进行数据可视化是数据分析和呈现的重要环节&#xff0c;R提供了多种强大的绘图系统和工具。以下是常见的数据可视化方法和示…...

编程日记 2025/7/22 11:58:09

NLP学习路线图（一）： 线性代数（矩阵运算、特征值分解等）

引言&#xff1a;语言与矩阵的奇妙邂逅 在自然语言处理&#xff08;NLP&#xff09;的魔法世界里&#xff0c;每个词语都像被施了变形术的精灵&#xff0c;在数学的殿堂中翩翩起舞。当我们用"king - man woman queen"这样的向量魔法破解语义密码时&#xff0c;线性…...

编程日记 2025/7/18 13:01:42

【滑动窗口】LeetCode 1004题解 | 最大连续1的个数 Ⅲ

最大连续1的个数 Ⅲ 一、题目链接二、题目三、题目解析四、算法原理解法一&#xff1a;暴力枚举 zero计数器解法二&#xff1a;滑动窗口 五、编写代码六、时空复杂度 一、题目链接 最大连续1的个数 Ⅲ 二、题目 三、题目解析 注意题目中说的是最多k次&#xff0c;在一个数组…...

编程日记 2025/7/24 20:49:41

Linux 内核等待机制详解：prepare_to_wait_exclusive 与 TASK_INTERRUPTIBLE

1. prepare_to_wait_exclusive 函数解析 1.1 核心作用 prepare_to_wait_exclusive 是 Linux 内核中用于将进程以独占方式加入等待队列的关键函数，其主要功能包括： 标记独占等待：通过设置 WQ_FLAG_EXCLUSIVE 标志，表明此等待条目是独占的。 安全入队：在自旋锁保护下，将条…...

编程日记 2025/7/24 5:32:33

分布式数据库TiDB：深度解析原理、优化与架构设计

&#x1f482; 个人网站:【 摸鱼游戏】【神级代码资源网站】【星海网址导航】 一、TiDB架构设计与核心原理 1.1 分布式架构演进 传统分库分表 vs TiDB架构 #mermaid-svg-8I88Hg2AVkzYTb3O {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fi…...

编程日记 2025/7/26 5:32:28

【深度学习基础】损失函数与优化算法详解：从理论到实践

【深度学习基础】损失函数与优化算法详解&#xff1a;从理论到实践 一、引言 1. 损失函数与优化算法在深度学习中的核心作用 在深度学习中&#xff0c;模型训练的本质是通过不断调整参数&#xff0c;使模型输出尽可能接近真实值。这一过程的核心驱动力是损失函数&#xff08;…...

编程日记 2025/7/25 18:52:01

睿抗足球机器人

目录 大框架 战术 Lua脚本语言编辑环境 大框架 策略脚本&#xff08;LUA-官方脚本&#xff09;、决策算法&#xff08;C-自定义&#xff09;、ROS系统 战术 我们研究了场地的长度、宽度、禁区范围、机器人运动速度等等&#xff0c;发现即使 Kicker 点球往极端角度踢&#xf…...

编程日记 2025/7/25 9:49:17

助力DBA技能无缝平迁 | YashanDB携最新成果亮相XCOPS智能运维管理人年会

5 月 16 日&#xff0c;由上海市软件行业协会、上海市计算机行业协会指导&#xff0c; dbaplus社群主办的XCOPS智能运维管理人年会在广州盛大召开&#xff0c;活动汇聚500余名金融、政府、能源、教育、电信、交通等领域的行业专家。深算院崖山数据库受邀参会&#xff0c;系统性…...

编程日记 2025/7/21 6:02:08

服务端安全测试：OWASP ZAP使用

ZAP下载地址：https://www.zaproxy.org/download/ ZAP有两种扫描方式： 1、使用 OpenAPI / Swagger 地址进行扫描 2、ZAP Proxy + Postman 因为业务云没有添加swagger插件所以本次介绍第2种方式。 【第一步】设置 ZAP 的代理端口（默认是 127.0.0.1:8080） 成功安装并打…...

编程日记 2025/7/25 7:33:06

Amazon Q 从入门到精通 – 测试与重构

Amazon Q Developer 是亚马逊推出的一个专为专业开发人员设计的人工智能助手&#xff0c;旨在提升代码开发和管理效率。其主要功能包括代码生成、调试、故障排除和安全漏洞扫描&#xff0c;提供一站式代码服务。 众所周知&#xff0c;在软件开发领域&#xff0c;测试代码是软件…...

编程日记 2025/7/25 9:44:39

[CSS3]属性增强2

空间转换 使用transform属性实现元素在空间内的位移、旋转、缩放等效果 空间: 是从坐标轴角度定义的。x、y 和z三条坐标轴构成了一个立体空间&#xff0c;z轴位置与视线方向相同。空间转换也叫3D转换 空间位移 使用translate实现元素空间位移效果 transform: translate3d(x…...

编程日记 2025/7/24 13:19:39

Go 语言 vs C+Lua（Skynet）游戏服务器方案对比分析

为啥挑这两个呢&#xff1f;因为两种技术分别对应CSP模型和Actor模型&#xff0c;都是经过时间检验的成熟且可靠的并发模型&#xff0c;问了很多地方&#xff0c;经过gpt整理得出如下报告。 从开发效率、运行性能、热更新扩展、云部署与水平扩展能力、多类型游戏支持等五个维度…...

编程日记 2025/7/22 2:16:16

ArcGIS Pro 3.4 二次开发 - 内容

环境&#xff1a;ArcGIS Pro SDK 3.4 .NET 8 文章目录 内容1 工程1.1 创建一个空工程1.2 使用指定名称创建新工程1.3 使用Pro的默认设置创建新工程1.4 使用自定义模板文件创建新工程1.5 使用 ArcGIS Pro 提供的模板创建工程1.6 打开现有工程1.7 获取当前工程1.8 获取当前工程的…...

编程日记 2025/7/24 2:35:50

java每日精进 5.19【Excel 导入导出】

基于 EasyExcel 实现 Excel 的读写操作&#xff0c;可用于实现最常见的 Excel 导入导出等功能。 Excel 导入导出功能涉及前后端协作&#xff0c;后端处理数据查询、文件生成和解析&#xff0c;前端提供用户交互和文件下载/上传界面。以下是全流程解析&#xff0c;分为导出流程…...

编程日记 2025/7/23 13:24:41

基于Elasticsearch的搜索引擎简介

## 一、Elasticsearch简介 Elasticsearch&#xff08;简称ES&#xff09;是一个开源的、分布式、RESTful风格的搜索和数据分析引擎&#xff0c;基于Apache Lucene开发。它能够实现对海量结构化和非结构化数据的实时存储、搜索和分析&#xff0c;广泛应用于全文检索、日志分析、…...

编程日记 2025/7/24 7:03:37

不同类型桥梁的无人机检测内容及技术难度

不同类型桥梁的无人机检测内容及技术难度 无人机桥梁检测的难度因桥梁类型、结构特点和所处环境的不同而存在显著差异。以下是针对梁桥、拱桥、斜拉桥、悬索桥等主要桥梁类型的无人机检测难度分析&#xff1a; 1. 梁桥&#xff08;简支梁、连续梁&#xff09; 检测难度&#x…...

编程日记 2025/7/18 4:45:55

数据结构实验10.1：内部排序的基本运算

文章目录 一&#xff0c;实验目的二&#xff0c;实验内容1. 数据生成与初始化2. 排序算法实现&#xff08;1&#xff09;直接插入排序&#xff08;2&#xff09;二分插入排序&#xff08;3&#xff09;希尔排序&#xff08;4&#xff09;冒泡排序&#xff08;5&#xff09;快速…...

编程日记 2025/7/25 21:13:47

java20

1.List集合 2.数据结构之栈&#xff0c;队列&#xff0c;数组&#xff0c;链表 3.ArrayList集合 4.LinkedList 5.泛型 注意&#xff1a;E...e是指若干个变量...

编程日记 2025/7/24 8:02:33

LLM笔记（九）KV缓存（2）

文章目录 1. 背景与动机2. 不使用 KV Cache 的情形2.1 矩阵形式展开2.2 计算复杂度 3. 使用 KV Cache 的优化3.1 核心思想3.2 矩阵形式展开3.3 计算复杂度对比 4. 总结5. GPT-2 中 KV 缓存的实现分析5.1 缓存的数据结构与类型5.2 在注意力机制 (GPT2Attention) 中使用缓存5.3 缓…...

编程日记 2025/7/23 18:11:41

将 Element UI 表格拖动功能提取为公共方法

为了在多个页面复用表格拖动功能&#xff0c;我们可以将其封装成以下两种形式的公共方法&#xff1a; 方案一&#xff1a;封装为 Vue 指令&#xff08;推荐&#xff09; 1. 创建指令文件 src/directives/tableDrag.js import interact from interactjs;export default {inse…...

编程日记 2025/7/25 18:52:45

项目中把webpack 打包改为vite 打包

项目痛点: 老vu e-cli1创建的项目,项目是ERP系统集成了很多很多管理,本地运行调试的时候,每次修改代码都需要等待3分钟左右的编译时间,严重影响开发效率. 解决方案: 采用vite构建项目工程 方案执行 第一步 使用vite脚手架构件一个项目,然后把build文件自定义的编译逻辑般到…...

编程日记 2025/7/25 12:56:52

Vue3 Element Plus 中el-table-column索引使用问题

在 Element Plus 的 el-table 组件中&#xff0c;使用 scope.index 是不准确的。正确的索引属性应该是 scope.$index。你的代码需要调整为&#xff1a; vue 复制 下载 <el-button type"primary" size"default" text click"onModifyClick(scope…...

编程日记 2025/7/21 19:37:39

盲盒一番赏小程序系统发展：创新玩法激发市场活力

盲盒一番赏小程序系统凭借其创新的玩法&#xff0c;在潮玩市场中脱颖而出&#xff0c;激发了市场的无限活力。它不仅保留了传统一番赏百分百中奖的特点&#xff0c;还结合线上平台的优势&#xff0c;开发出了更多新颖的玩法。 例如&#xff0c;小程序系统设置了赏品回收功能。…...

编程日记 2025/7/22 9:33:36

MySQL故障排查

目录 MySQL 单示例故障排查 故障现象一​ 故障现象二 故障现象三 故障现象四 故障现象五 故障现象六 故障现象七 故障现象八 MySQL主从复制排查 故障现象一 故障现象二 故障现象三 MySQL 优化 硬件方面 关于CPU 关于内存 关于磁盘 MySQL配置文件 核…...

编程日记 2025/7/24 1:04:21

微服务项目-＞在线oj系统(Java版 - 4)

相信自己,终会成功 目录 B端用户管理 C端用户代码 发送验证码: 验证验证码 退出登录 登录用户信息功能 用户详情与用户编辑 用户竞赛接口 用户报名竞赛 用户竞赛报名接口查询 用户信息列表 ThreadLocalUtil Hutool工具库 常用功能介绍 B端用户管理 进行列表显示与…...

编程日记 2025/7/23 20:57:09

DDoS与CC攻击：谁才是服务器的终极威胁？

在网络安全领域&#xff0c;DDoS&#xff08;分布式拒绝服务&#xff09;与CC&#xff08;Challenge Collapsar&#xff09;攻击是两种最常见的拒绝服务攻击方式。它们的目标都是通过消耗服务器资源&#xff0c;导致服务不可用&#xff0c;但攻击方式、威胁程度和防御策略存在显…...

编程日记 2025/7/25 10:29:25

旧物回收小程序，一键解决旧物处理难题

在快节奏的现代生活中&#xff0c;我们常常会面临旧物处理的困扰。扔掉觉得可惜&#xff0c;留着又占空间&#xff0c;而且处理起来还十分麻烦。别担心&#xff0c;我们的旧物回收小程序来啦&#xff0c;只需一键&#xff0c;就能轻松解决你的旧物处理难题&#xff01; 这款小…...

编程日记 2025/7/24 23:42:09

uniapp小程序获取手机设备安全距离

utils.js let systemInfo null;export const getSystemInfo () > {if (!systemInfo) {systemInfo uni.getSystemInfoSync();// 补充安全区域默认值systemInfo.safeAreaInsets systemInfo.safeAreaInsets || {top: 0,bottom: 0,left: 0,right: 0};// 确保statusBarHei…...

编程日记 2025/7/25 20:12:16

小程序弹出层/抽屉封装 （抖音小程序）

最近忙于开发抖音小程序&#xff0c;最想吐槽的就是&#xff0c;既没有适配的UI框架&#xff0c;百度上还找不到关于抖音小程序的案列&#xff0c;我真的很裂开啊&#xff0c;于是我通过大模型封装了一套代码 效果如下 介绍 可以看到 这个弹出层是支持关闭和标题显示的&#xf…...

编程日记 2025/7/23 12:11:07

map与set封装

封装map和set一般分为6步&#xff1a; 1.封装map与set 2.普通迭代器 3.const 迭代器 4.insert返回值处理 5.map operator【】 6.key不能修改的问题 一.红黑树的改造 map与set的底层是通过红黑树来封装的&#xff0c;但是map与set的结点储存的值不一样&#xff0c;set只需要存…...

编程日记 2025/7/24 19:20:21

【C语言基础语法入门】通过简单实例快速掌握C语言核心概念

文章目录 1. Hello World&#xff1a;第一个C程序2. 变量与数据类型3. 运算符4. 控制结构4.1 if-else 条件判断4.2 for 循环4.3 while 循环 5. 函数6. 数组7. 指针8. 结构体总结 &#x1f4e3;按照国际惯例&#xff0c;首先声明&#xff1a;本文只是我自己学习的理解&#xff0…...

编程日记 2025/7/22 17:32:45