eJOI2019 Problem B. Hanging Rack 题解

问题分析

我们有一棵 $n$ 层的满二叉树，叶子节点从左到右编号为 $1$ 到 $2^n$。
每个非叶子节点有一个约束：左右子树上挂的衣服数量差 $w_l - w_r \in \{0, 1\}$（即左子树最多比右子树多一件衣服）。
我们需要找出按照这个约束，第 $k$ 件衣服应该挂在哪个叶子节点上。

关键观察：这个约束实际上定义了一个确定的挂衣服顺序，我们需要找到这个顺序中的第 $k$ 个位置对应的叶子编号。

深入理解约束条件

对于每个非叶子节点：

• 初始时 $w_l = w_r = 0$
• 每次挂衣服后，必须满足 $w_l - w_r \in \{0, 1\}$
• 这意味着：
  1. 如果 $w_l = w_r$，那么下一件衣服必须挂在左子树上（因为如果挂右子树，$w_l - w_r$ 会变成 $-1$，不合法）
  2. 如果 $w_l = w_r + 1$，那么下一件衣服必须挂在右子树上（以恢复平衡）

所以，对于每个节点，挂衣服的顺序是确定的：先左，再右，再左，再右，...，交替进行。

递归结构

考虑以节点 $u$ 为根的子树，该子树总共有 $m$ 件衣服要挂（即最终该子树会挂 $m$ 件衣服）。
设 $u$ 的左子树大小为 $L$（叶子数），右子树大小为 $R$（叶子数，满二叉树中 $L = R$）。

当要在 $u$ 的子树中挂 $m$ 件衣服时：

• 根据约束，分配方式为：左子树 $\lceil m/2 \rceil$ 件，右子树 $\lfloor m/2 \rfloor$ 件
• 这是因为必须始终保持 $w_l - w_r \in \{0, 1\}$

重要推论：挂衣服的顺序由递归决定：

1. 第 $1$ 件衣服总是挂在左子树中
2. 第 $2$ 件衣服总是挂在右子树中
3. 第 $3$ 件衣服总是挂在左子树中
4. 以此类推...

递归算法

我们可以设计一个递归函数 solve(node, k, n)：

• node：当前考虑的子树根节点对应的叶子编号范围的起点
• k：要在当前子树中挂的第几件衣服（从 1 开始）
• n：当前子树的高度（层数）

递归过程：

1. 如果 $n = 0$（到达叶子），返回 node
2. 否则：
   • 计算中间点：mid = node + 2^(n-1)（左子树范围：[node, mid-1]，右子树范围：[mid, node + 2^n - 1]）
   • 如果 $k$ 是奇数：第 $k$ 件衣服挂在左子树，递归调用 solve(node, (k+1)/2, n-1)
   • 如果 $k$ 是偶数：第 $k$ 件衣服挂在右子树，递归调用 solve(mid, k/2, n-1)

证明：

• 当 $k$ 是奇数时，这是该节点左子树中的第 $\lceil k/2 \rceil = (k+1)/2$ 件衣服
• 当 $k$ 是偶数时，这是该节点右子树中的第 $k/2$ 件衣服

非递归实现

由于 $n$ 可能很大（$10^6$），递归可能导致栈溢出。我们可以使用迭代方法：

令当前叶子编号起点为 pos = 1 对于层数从 $n$ 递减到 $1$：

• 如果 $k$ 是奇数：衣服挂在左子树，pos 不变，k = (k+1)/2
• 如果 $k$ 是偶数：衣服挂在右子树，pos += 2^(当前层数-1)，k = k/2

最后 pos 就是答案（需要取模）。

快速幂取模

由于 $2^n$ 可能很大（$n \le 10^6$），我们需要快速计算 $2^{n-1} \bmod M$，其中 $M = 10^9+7$。
使用快速幂算法可以在 $O(\log n)$ 时间内计算，但 $n$ 很大时 $\log n$ 约 20，可以接受。

更优方法：预处理 $2^i \bmod M$ 的值，因为我们需要 $2^{i}$ 对于 $i = 0$ 到 $n-1$。

算法步骤

1. 预处理 pow2[i] = 2^i mod M，$i = 0$ 到 $n$
2. 初始化 pos = 1（模 M）
3. 对于 level 从 n 递减到 1：
   • 如果 k 是奇数：
     • k = (k+1)/2
   • 否则（k 是偶数）：
     • pos = (pos + pow2[level-1]) % M
     • k = k/2
4. 输出 pos

注意：$k$ 可能非常大（$10^{18}$），需要用 long long 存储。

复杂度分析

• 时间复杂度：$O(n)$，需要迭代 $n$ 层
• 空间复杂度：$O(n)$ 存储 pow2 数组，或 $O(1)$ 使用快速幂每次计算

完整 C++ 实现

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MOD = 1000000007;

// 快速幂：计算 2^exp mod MOD
ll fast_pow2(int exp) {
    ll res = 1;
    ll base = 2;
    while (exp > 0) {
        if (exp & 1) {
            res = (res * base) % MOD;
        }
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    ll k;
    cin >> n >> k;
    
    // 预处理 2^i mod MOD
    vector<ll> pow2(n + 1);
    pow2[0] = 1;
    for (int i = 1; i <= n; i++) {
        pow2[i] = (pow2[i-1] * 2) % MOD;
    }
    
    ll pos = 1; // 当前叶子编号的起点（模 MOD）
    
    for (int level = n; level >= 1; level--) {
        if (k % 2 == 1) {
            // 奇数：挂在左子树
            k = (k + 1) / 2;
        } else {
            // 偶数：挂在右子树
            k = k / 2;
            // 移动到右子树的起点
            pos = (pos + pow2[level - 1]) % MOD;
        }
    }
    
    // 此时 pos 就是答案
    cout << pos % MOD << endl;
    
    return 0;
}

优化版本（减少内存）

我们可以不存储整个 pow2 数组，而是使用快速幂即时计算：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MOD = 1000000007;

ll mod_pow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    ll k;
    cin >> n >> k;
    
    ll pos = 1;
    
    // 预计算 2^i mod MOD，从最高位开始
    // 我们可以倒序计算，每次计算 2^(level-1)
    for (int level = n; level >= 1; level--) {
        if (k % 2 == 1) {
            k = (k + 1) / 2;
        } else {
            k = k / 2;
            // 计算 2^(level-1) mod MOD
            ll add = mod_pow(2, level - 1);
            pos = (pos + add) % MOD;
        }
    }
    
    cout << pos << endl;
    
    return 0;
}

正确性验证

样例1

n=3, k=2
初始：pos=1, level=3, k=2(偶)
level=3: k偶 → pos=1+2^2=1+4=5, k=1
level=2: k奇 → k=1, pos不变
level=1: k奇 → k=1, pos不变
结果：5 ✓

样例2

n=5, k=10
模拟过程：
level=5: k=10(偶) → pos=1+2^4=17, k=5
level=4: k=5(奇) → k=3, pos不变
level=3: k=3(奇) → k=2, pos不变
level=2: k=2(偶) → pos=17+2^1=19, k=1
level=1: k=1(奇) → k=1, pos不变
结果：19 ✓

数学解释

这个算法本质上是将 $k$ 表示为二进制，然后根据二进制位决定路径：

• 从最高位开始（对应树的根）
• 如果当前位是 1（对应 $k$ 奇数），走左子树
• 如果当前位是 0（对应 $k$ 偶数），走右子树，并加上相应的偏移量

实际上，最终叶子编号可以表示为：

$$\text{pos} = 1 + \sum_{i: \text{第i步走右子树}} 2^{n-i}$$

其中 $i$ 从 1 到 $n$。

扩展思考

1. 逆问题：给定叶子编号 $x$，求它是第几件衣服挂上去的？
2. 批量查询：多次查询不同的 $k$，如何优化？
3. 动态版本：支持插入和删除衣服，如何维护？

对于逆问题，可以通过类似的递归解决：从叶子向上回溯，根据当前节点是左孩子还是右孩子决定 $k$ 的计算方式。

总结

本题的关键在于理解约束条件导致确定的挂衣顺序，并将问题转化为递归/迭代的路径选择问题。通过分析奇偶性，我们得到了高效的 $O(n)$ 算法，可以处理 $n \le 10^6$ 的大数据范围。算法实现简单，但需要深刻理解问题背后的递归结构。