Uva 679 Dropping Balls (模拟/二叉树的编号)

题意：有一颗二叉树，深度为D，所有节点从上到下从左到右编号为1，2，3.....在结点一处放一个小球，每个节点是一个开关，初始全是关闭的，小球从顶点落下，小球每次经过开关就会把它的状态置反，现在问第k个球下落到D层时经过的开关编号

思路：lrj大哥的书上第一种方法是模拟，但是还是有要知道的知识点，对于一个结点k，其左子结点为2k,右结点为2k+1，它的父节点为k/2，深度为d的一颗树包含2^d个结点； 第二种方法，由于第一中方法模拟的运算量太大，所以我们lrj大哥说当I是奇数时，它是往左走的第（I+1)/2个小球，当I是偶数时，它是往右走第I/2个小球~

代码：

第一种：

#include <bits/stdc++.h>

using namespace std;
const int maxd=20;
int visit[1<<maxd];

int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        int go,k=(1<<n)-1;
        memset(visit,0,sizeof(visit));
        for(int i=0;i<m;i++)
        {
            go=1;
            for(;;)
            {
                if(visit[go]==0)
                {
                    visit[go]=1;
                    go=go*2;
                }
                else
                {
                    visit[go]=0;
                    go=go*2+1;
                }
                if(go>k) break;
            }
        }
        cout<<go/2<<endl;
    }
    return 0;
}

第二种：

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
  int D,I;
  while(cin>>D>>I){
     int k=1;
     for(int i=0;<D-1;i++){
         if(I%2){
         k=k*2;
         I=(I+1)/2;
         }
         else {
         k=k*2+1;
         I=I/2;
         }
     }
     cout<<k<<endl;
  }
  return 0;
}