一本通-1363：小球(drop)（满二叉树性质应用）

【题目描述】 许多的小球一个一个的从一棵满二叉树上掉下来组成FBT（Full Binary Tree，满二叉树），每一时间，一个正在下降的球第一个访问的是非叶子节点。然后继续下降时，或者走右子树，或者走左子树，直到访问到叶子节点。决定球运动方向的是每个节点的布尔值。最初，所有的节点都是false，当访问到一个节点时，如果这个节点是false，则这个球把它变成true，然后从左子树走，继续它的旅程。如果节点是true，则球也会改变它为false，而接下来从右子树走。满二叉树的标记方法如下图:

因为所有的节点最初为false，所以第一个球将会访问节点1，节点2和节点4，转变节点的布尔值后在在节点8停止。第二个球将会访问节点1、3、6,在节点12停止。明显地，第三个球在它停止之前，会访问节点1、2、5，在节点10停止。

现在你的任务是，给定FBT的深度D，和I，表示第I个小球下落，你可以假定I不超过给定的FBT的叶子数，写一个程序求小球停止时的叶子序号。

【输入】 一行包含两个用空格隔开的整数D和I。其中2≤D≤20，1≤I≤524288。

【输出】 对应输出第I个小球下落停止时的叶子序号。

【输入样例】 4 2

【输出样例】 12

---

这道题同时还是《算法竞赛入门经典》的6.3二叉树中的题目。

首先来估算数据范围，其中深度最大是20，那么意味着节点的数目是$2^{20}\approx 10^6$，所以如果是模拟的化，开这么大的数组也是没问题的，由于每个小球都要走二叉树的深度的次数，所以时间复杂度是$6 \times 10^ 6 \times 20 = 1.2 \times 10^7$，所以还是在时间限制范围内的。

模拟的方法：由于题目指明是满二叉树，满二叉树一个很重要的性质是左右子节点和父节点存在对应关系，设父节点下标为k，左子节点下标为2k，右子节点下标为2k+1。

#include <bits/stdc++.h>

using namespace std;

vector<bool> node(2 * 1e6, false);
int n;

int solve(int num)
{
    int curPos = 1, prePos = 1;
    for (int i = 1; i <= num; ++i) {
        curPos = 1, prePos = 1;
        while (curPos <= n) {
            if (node[curPos]) {
                node[curPos] = false;
                prePos = curPos;
                curPos = curPos * 2 + 1;
            }
            else {
                node[curPos] = true;
                prePos = curPos;
                curPos <<= 1;
            }
        }
    }

    return prePos;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int depth, num; cin >> depth >> num;
    n = (1 << depth) - 1; //满二叉树全部节点的个数

    cout << solve(num) << endl;

    return 0;
}

第二种方法：在《算法竞赛入门经典》里面，给出了一种很巧妙的实现，非常类似于约瑟夫环这种类型，往往存在着简单的解法。我们发现对于根节点，也就是标号为1的节点，它为true还是false只和奇偶有关，也就是第一个小球时是false，第三个小球是false。然后类似递归的去解决，比如标号为2的节点，很显然，只有标号为奇数的小球才会落在左子树2，然后我们对这些小球“重新编号”，那么第一个小球是1，第三个小球是2，相当于递归的去解决问题了。这样做的一个好处是根本不需要去开一个大数组去存储树上每个节点的状态，也不需要去做一些没有用处的模拟。另外如果是多组输入的情况下，很显然第二种方法更能节省时间。

#include <bits/stdc++.h>

using namespace std;



int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int depth, num;
    cin >> depth >> num;

    int k = 1;
    for (int i = 0; i < depth - 1; ++i) {
        if (num & 1) { //小球标号为奇数
            k <<= 1; num = ((num + 1) >> 1);
        }
        else { //小球标号为偶数
            k = k * 2 + 1; num >>= 1;
        }
    }
    cout << k << endl;

    return 0;
}