UVA.679 Dropping Balls （二叉树 思维题）

题意分析

给出深度为D的完全二叉树，按照以下规则，求第I个小球下落在那个叶子节点。

1. 默认所有节点的开关均处于关闭状态。

2. 若有小球下落在关闭状态的节点时，走向其左子树，否则走向其右子树。

3. 小球下落到某个节点，通过后开关反转。

模拟肯定不行，要根据树的特点和下落规则找简单办法。首先一个球下来，开关的状态要么是开要么是关，而且是交替进行，于是小球走的方向，是与小球是当前节点第几个球是有关系的。不难发现，对于每一个节点来说，若这个小球是其奇数个球，那么就会走向左子树，若是偶数个球，则会走向其右子树。根据这条性质，便可以直接模拟最后一个小球的走向。

代码总览

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int main()

{

    int kase;

    while(scanf("%d",&kase) && kase !=-1){

        while(kase --){

            int D ,I ;

            scanf("%d%d",&D,&I);

            int k =1;

            for(int i = 0;i<D-1; ++i){

                if(I%2) {k  = k*2; I = (I+1)/2;}

                else{k = k*2 +1; I/=2;}

            }

            printf("%d\n",k);

        }

    }

    return 0;

}