专栏文章

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

2025/10/27 20:51P4785题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论: 1 条
当前快照: 1 份
快照标识符: @minhbtc7
此快照首次捕获于: 2025/12/02 02:25
此快照最后确认于: 2025/12/02 02:25

题目描述

给定一个

n

个点的完全二叉树，每次操作可以选择是否交换节点

k

与其父亲节点。

对于节点

i

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

保持不变
$i$ 与左儿子交换
$i$ 与右儿子交换
$i$ 变成右儿子，左儿子变为 $i$ ，右儿子变为左儿子

解题思路

关键观察

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

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

方法一：贪心

按照

1 \sim n

的顺序贪心，每个点只有

O(\log n)

种可能的取值。

将节点分为三类：

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

时间复杂度：

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)

（取决于实现）

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...