首页 > 代码库 > UVa 679 - Dropping Balls

UVa 679 - Dropping Balls

题目:有一颗满二叉树,每个节点是一个开关,初始全是关闭的,小球从顶点落下,

            小球每次经过开关就会把它的状态置反,现在问第k个球下落到d层时经过的开关编号。

分析:进制编码。经过模拟几次可以看出,球会让开关形成连续二进制数的表示(根是低位)。

            当放入第k个球时,开关状态正好是二进制的k,利用模2的余数判断走向即可。

说明:观察规律模拟处理即可。

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

using namespace std;

int main()
{
	int n,r,l;
	while (cin >> n && n >= 0) {
		while (n --) {
			cin >> l >> r;
			int k = 1;
			while (-- l) {
				if (r%2) k = k<<1;
				else k = (k<<1)+1;
				r = (r+1)>>1;
			}
			cout << k << endl;
		}
	}
	return 0;
}

UVa 679 - Dropping Balls