一、题意

每组数组为一棵树，给出这个数的深度D，以及小球数量I。
每个球从一个二叉树根开始沿着树干下落，每经过一个结点会改变结点的开闭状态。所有结点的默认状态为关闭。关闭时小球往左走，否则往右走。
求每组数据中，第I个小球会落在那个叶子结点中。结点编号按层次遍历1到2^D-1。

二、解析

考察二进制的概念。假设是第I个小球，I从0开始算起的话，则I的二进制末位为0则往左走，1则往右走，每下一层I往右移一位。
然后根据树结点编号的计算方法即可算出答案。

三、代码

#include <iostream>
using namespace std;

int main() {
    int n, D, I, end;
    cin >> n;
    while(n --) {
        cin >> D >> I;
        D --, I --;
        long long ans = 1;
        while(D --) {
            if(I % 2) ans = ans * 2 + 1;
            else ans *= 2;
            I >>= 1;
        }
        cout << ans << endl;
    }
    cin >> end;
}

四、归纳

  • 主要复习了二进制，通常二进制可以结合状态压缩用来加快算法。
  • 复习了树的操作。在从1开始层次遍历编号的书中，i * 2 + 1得到右子结点，i * 2得到左子节点。i / 2得到父节点。