UVA 679 Dropping Balls

题目：

　　有一颗满二叉树，每个节点是一个开关，初始全是关闭的，小球从顶点落下.小球每次经过开关就会把它的状态置反，现在问第k个球下落到d层时经过的开关编号。

分析：

　　球会让开关形成连续二进制数的表示（根是低位）。本来用数组模拟，但超时，后来找到规律。当放入第k个球时，开关状态正好是二进制的k，利用模2的余数判断走向即可。

代码：

　　

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=20;
int main()
{
    int t;
    while(scanf("%d",&t))
    {
        if(t<0)
            break;
        while(t--)
        {
            int D,I;
            scanf("%d%d",&D,&I);
            int k=1;
            while(--D)
            {
                if(I%2)
                    k=k<<1;
                else
                    k=(k<<1)+1;
                I=(I+1)>>1;
            }
            cout<<k<<endl;
        }
    }
}