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

CF2154D

给定一棵大小为 \(n\) 的树,需要构造不超过 \(3n\) 条指令(有以下两种,且不能有连续两次 \(2\) 操作),使得一个在 \(1\) 的棋子一定能走到 \(n\)

  • \(1\),表示棋子会移动到一个和它相邻的节点,没有则不移动。
  • \(2 \ u\),表示摧毁节点 \(u\) 及其邻边,需保证棋子不在 \(u\)

\(1h\)

首先如何保证进行而操作时棋子不在 \(u\) ?

有一种自然的想法,因为树是一种二分图,按照深度的奇偶性分成两个集合,只需要保证此前执行的 \(1\) 操作次数的奇偶性与 \(u\) 的深度不一样即可。

我们应该先将除 \(1 \rightarrow u\) 的点先删干净。因为每次删一个叶子不会使棋子与 \(n\) 处于两个连通块内,所以优先删叶子节点,即深度较大的点。假设执行 \(c\) 次一操作,就删深度奇偶性为 \((c \& 1) \oplus 1\) 中最大的点即可,如果没有可以进行一操作然后再删深度为 \(c \& 1\) 的点,显然每个点不会花费超过 \(3\) 次操作。

对于路径上的点,先保证棋子不在 \(u\),即至少在 \(u\) 的儿子(通过至多一次 \(1\) 操作办到),然后删去 \(u\),再挪棋子即可。

时间复杂度:\(O(n)\)

http://www.hskmm.com/?act=detail&tid=37671

相关文章:

  • Plya 定理学习笔记 | ABC428G 题解
  • 第十八天
  • 第十七天
  • vue3+elementPlus el-date-picker 自定义禁用状态hook 建立结束时间不能小于开始时间
  • [优先队列] P3611 [USACO17JAN] Cow Dance Show S 题解
  • 搜维尔科技将携手Xsens|Haption|Tesollo|Manus亮相IROS 2025国际智能机器人与系统会议
  • 【做题记录】贪心--提高组
  • 如何炫酷地使用集合划分容斥
  • 简单云计算算法--20251023
  • 处理空输入踩的坑
  • latex输入公式
  • 【为美好CTF献上祝福】 New Star 2025 逆向笔记
  • XXL-JOB(5)
  • 蛋白表达原理与关键要素解析
  • Ramanujan Master Theorem
  • 顾雅南的声音美化课堂
  • C++案例 自定义数组
  • 【周记】2025.10.13~2025.10.19
  • 背包
  • 10.23《程序员修炼之道 从小工到专家》第二章 注重实效的途径 - GENGAR
  • 玩转单片机之智能车小露——LED闪烁实战
  • ord() 函数
  • 2025.10.23总结 - A
  • 大模型 | VLA 初识及在自动驾驶场景中的应用
  • ExPRT.AI如何预测下一个将被利用的漏洞
  • Redis中的分布式锁之SETNX底层实现
  • 攻击模拟
  • 2025家纺摄影公司推荐,南通鼎尚摄影专注产品视觉呈现
  • AI元人文构想的跨学科研究:技术实现与人文影响分析——对自由与责任的再框架化(DeepSeek基于Ai元人文系列文章研究)
  • Python---简易编程解决工作问题