UVa - 679 - Dropping Balls(完全二叉树编号)

一棵深度为D满二叉树层次遍历编号从1到2^D-1，有X个小球一次从1掉落，可以掉落到左子树或者右子树，每一个内部结点都有一个开关，起初开关都是关闭着的，当小球进入结点后，如果开关是关闭，则开关改变成为开，小球落入左子树，相反同理。现在给出D和X求出第X个小求落在的结点编号。

思路:经过一两次模拟后，发现：在根节点时，奇数y个小球总是落在左子树，并且是第(y+1)/2个落入该左子树的。偶数y个小球总是落在右子树，并且是第y/2个落入该右子树。因此小球最后落入的结点的编号只与第X个小球，X的奇偶性有关，所以直接模拟最后一个小球的掉落过程即可得出答案。

#include<cstdio> using namespace std; int main(){ freopen("input.txt","r",stdin); int d,I,t; while(scanf("%d",&t)==1){ if(t==-1)break; for(int i=0 ;i<t ;i++){ int k = 1; scanf("%d%d",&d,&I); for(int i=0 ;i<d-1 ;i++){ if(I%2){k = 2*k; I = (I+1)/2;}//奇数 else{k = 2*k+1; I = I/2;}//偶数 } printf("%d\n",k); } } return 0; }