小球(drop)

题目描述

一棵深度为 $D$ 的满二叉树按层序编号：根为 $1$ ，节点 $k$ 的左孩子是 $2k$ 、右孩子是 $2k+1$ 。小球从根出发逐层下落：每个节点带一个初始为 false 的布尔值，球到达节点时把它翻转——翻转前为 false 则走左子树，为 true 则走右子树，直到落在叶子上。输入一行两个整数 $D$ 和 $I$ （ $2 \leqslant D \leqslant 20$ ， $I$ 不超过叶子数 $2^{D-1}$ ），输出第 $I$ 个小球停止时的叶子编号。例如深度 $D=4$ 时，第 1、2、3 个球分别停在节点 8、12、10；样例输入 4 2，输出 12。

思路

所有球都要经过根，所以第 $I$ 个球就是第 $I$ 个到达根的球；第 $j$ 个到达某节点的球遇到的标记值为 $(j-1)\bmod 2$ ，因此 $j$ 为奇数走左、偶数走右，且这一判断只依赖本节点的到达序号。于是只需维护一个序号： $I$ 为奇数走左子节点、偶数走右子节点，然后走左的球占前 $\lceil I/2\rceil$ 个序号、走右的占后一半，序号更新为 $(I+\text{走左})/2$ ，逐层进行 $D-1$ 次即得叶子编号，时间 $O(D)$ 、空间 $O(1)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 07:16
# update_at: 2026-10-12 14:55

# 满二叉树小球下落：不建树、不模拟布尔标记，奇偶折半直接定位叶子。
# 所有球都经过根，第 I 个球就是第 I 个到达根的球；第 j 个到达某结点的球，
# j 为奇数走左、偶数走右，走左的球占前一半序号、走右的占后一半。
# 所以只需跟踪"第几个球在当前子树里的序号"，逐层折半，走 depth-1 层即落在叶子上。
# 如何使用：
# 1. leaf_of(depth, index)  # 第 index 个小球停下的叶子序号（满二叉树按层序编号）
# 2. solve()                # 读入一行 D I，打印叶子序号

import sys


def leaf_of(depth: int, index: int) -> int:
    """第 index 个小球停下的叶子序号：每层用 index 的奇偶定方向，再把 index 折半。"""
    node = 1
    for _ in range(depth - 1):  # 从根往下走 depth-1 层到达叶子
        go_left = index & 1  # 该结点第奇数次被访问的球走左，偶数次走右
        node = 2 * node + (1 - go_left)  # 左孩子 2k、右孩子 2k+1
        index = (index + go_left) >> 1  # 走左的球挤进前一半序号，走右的落到后一半
    return node


def solve() -> None:
    depth, index = map(int, sys.stdin.buffer.read().split())
    print(leaf_of(depth, index))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 12:07
 * update_at: 2026-10-12 14:55
 */
// main.cpp：满二叉树小球下落：奇偶折半递推直接定位叶子，O(D) 时间、O(1) 空间。
//
// 不建树、不模拟每个结点的布尔标记：所有球都经过根，第 I 个球就是第 I 个到达根的球；
// 第 j 个到达某结点的球，j 为奇数走左、偶数走右，走左的球占前一半序号、走右的占后一半。
// 所以只需跟踪"第几个球在当前子树里的序号"，逐层定方向并折半，走 D-1 层即落在叶子上
// （满二叉树按层序编号：结点 k 的左孩子 2k、右孩子 2k+1）。

#include <cstdio>

typedef long long ll;

ll depth; // 满二叉树的深度 D（2 ≤ D ≤ 20），从根到叶子要走 depth-1 层
ll ball;  // 小球序号 I（1 ≤ I ≤ 524288，不超过叶子数 2^(D-1)）

// 求第 ball 个小球停下时的叶子编号：每层用序号的奇偶定方向，再把序号折半
ll find_leaf(ll depth, ll ball) {
    ll node = 1; // 当前所在结点编号，根是 1
    for (ll i = 1; i <= depth - 1; i++) {
        ll go_left = ball & 1; // 该结点第奇数次被访问的球走左，偶数次走右
        node = 2 * node + (1 - go_left);
        ball = (ball + go_left) >> 1; // 走左的球挤进前一半序号，走右的落到后一半
    }
    return node;
}

// 读入 D、I，输出第 I 个小球停止时的叶子序号
void solve() {
    scanf("%lld %lld", &depth, &ball);
    printf("%lld\n", find_leaf(depth, ball));
}

int main() {
    solve();
    return 0;
}

目录

题目描述

思路

参考代码