算法竞赛入门经典chapter6：二叉树~小球下落

样例输入：

4 2

3 4

10 1

2 2

8 128

16 12345

样例输出：

512

255

36358

My Code

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn = 20;
 4 
 5 int node[1<<maxn];
 6 int main()
 7 {
 8     int d, n;
 9     while(cin >> d >> n)
10     {
11         int s = 1<<d;
12         memset(node, 0, s);//初始化结点全部关闭
13         int i;
14         while(n--)//n个小球
15         {//结点状态为关闭则向左走，否则，向右走
16             for(i = 1;  i < s; i = (!node[i]?(2*i+1):(2*i)))//注意：此处为结点的为改变之前的状态
17                 node[i] = (node[i] ? 0 : 1);//改变结点状态
18         }
19         cout << (i+1)/2 << endl;
20     }
21     return 0;
22 }

每个小球都会落在根节点上，因此前两个小球必然是一个在左子树，一个在右子树。一般地，只需看小球编号的奇偶性，就能知道它是最终在哪棵子树中。对于那些落入根节点左子树的小球来说，只需知道该小球是第几个落在根的左子树里的，既可以知道它下一步往左还是往右了。以此类推，直到小球落到叶子上。

如果使用题目中给出的编号n，则当I是奇数时，它是往左走的第（n+1）/2个小球；当I是偶数时，它是往右走的对n/2个小球。这样，可以直接模拟最后一个小球的路线。改进如下

Better

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int d, n;
 7     while(cin >> d >> n)
 8     {
 9         int k = 1;
10         for(int i = 0; i < d-1; i++)
11             if(n%2)
12             {
13                 k *= 2;
14                 n = (n+1)/2;
15             }
16             else
17             {
18                 k = k*2+1;
19                 n /= 2;
20             }
21             cout << k << endl;
22     }
23     return 0;
24 }

优点是省略了一个巨大的数组。