题解：P4785 [BalticOI 2016] 交换 (Day2)

Him_shu · 2025-10-27 20:51:15 · 题解

题目描述

给定一个 n 个点的完全二叉树，每次操作可以选择是否交换节点 k 与其父亲节点。

对于节点 i，考虑其与左右儿子的交换，有 4 种可能情况：

1. 保持不变

解题思路

关键观察

一个节点的取值可能来自：

• 某个儿子节点
• 包含自己在内的某个祖先节点
• 某个祖先 u 的兄弟节点 v（要求 u 是其父亲的右儿子）

方法一：贪心

按照 1 \sim n 的顺序贪心，每个点只有 O(\log n) 种可能的取值。

将节点分为三类：

1. 取值不来自儿子：祖先节点不能换到后代节点，左右子树不能交换
2. 取值来自左儿子：祖先节点有且仅有一个能换到左儿子上，祖先和左子树不会与右子树交换
3. 取值来自右儿子：祖先节点有一个可以换到子树内，左儿子也能换到右子树内

时间复杂度：O(n\log n)

方法二：动态规划

设 f(x, i) 表示当节点 x 的值为 i 时，i 最后所在的位置。

转移时，当遇到右儿子最小的情况（假设 i < a_{ls}），我们希望将 i 排得靠前，只需比较 f(ls, i) 和 f(rs, i) 的大小。

状态数：O(n\log n)
时间复杂度：O(n\log n) 或 O(n\log^2 n)（取决于实现）