首页 > 代码库 > UVa 679小球下落(二叉树的编号)

UVa 679小球下落(二叉树的编号)

题意:二叉树按层次遍历从1开始标号,所有叶子结点深度相同,每个结点开关初始状态皆为关闭,小球从根结点开始下落(小球落在结点开关上会使结点开关状态改变),若结点开关关闭,则小球往左走,否则往右走,给定二叉树深度D,求第I个小球所落到的叶子结点编号。

分析:对于每一个结点,若小球当前编号为k,

k为奇数,则这个小球是第(k+1)/2个落在此处的,则往左走;

k为偶数,则这个小球是第k/2个落在此处的,则往右走;

从根结点到叶子结点需判断D-1次。

比如,假如I为15,则这是第15个落在根结点的小球,是第8个需在根结点往左走的小球,也是第8个到达根结点的左孩子结点的小球,也是第4个需在根结点的左孩子结点处往右走的小球,依次类推。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
typedef long long ll;
typedef unsigned long long llu;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {0, 0, -1, 1};
const int dc[] = {-1, 1, 0, 0};
const double pi = acos(-1.0);
const double eps = 1e-8;
const int MAXN = 530000 + 10;
const int MAXT = 1000000 + 10;
using namespace std;
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        int D, I;
        scanf("%d%d", &D, &I);
        int ans = 1;
        for(int i = 0; i < D - 1; ++i){
           if(I & 1){
                ans <<= 1;
                I = (I + 1) >> 1;
           }
           else{
                ans = ans * 2 + 1;
                I >>= 1;
           }
        }
        printf("%d\n", ans);
    }
    scanf("%d", &T);
    return 0;
}

 

UVa 679小球下落(二叉树的编号)