UVa 679 例题6-6 小球下落（Dropping Balls）

原题链接： UVa-679

题目大意：

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

解题思路：

 这道题一开始看的时候，感觉不是很复杂，看了题目就开始自己实现了。

 （代码一）一开始（为什么说一开始，因为后面还有另一方法啊！）思路很直接，就是用一个2^m大小的数组来模拟二叉树，第i个位置的左右节点分别是i*2和i*2+1.然后模拟从1到n个小球的下落过程。最后就能顺利获得最后一个小球的下落位置了。（代码一）

 （非重点，吐槽）是不是很简单？昂？当时感觉真爽啊!写完一个bug都没啊！直接出正确结果啊！debug都不用啊！果然写水题很有成就感啊！然后就准备提交，为了以防万一我还在Udebug上找了一组输入测试了一下。通过！爽！然后就提交了，心里默想不AC我直播吃屎。（划掉，为什么要划掉呢，因为我没说过啊，哈哈哈）然后，然后，然后就TLE了。（你在逗我吧，怎么可能不AC，一定是OJ出毛病了，烂OJ,恩，绝对是这样。）然后我就去看紫书上的代码，这么思路完全和我的一样啊，那为毛不能AC啊，吃屎吧！然后直到我开始翻下一页，MMP，竟然还可以这样，吃屎吧你。。。

 （代码二）另一种更优的思路是，当一个小球在某个结点时，可以直接根据该小球是第几个落在该结点上的来判断他的下落方向，如果是如果是奇数则应该落到他的左结点，如果是奇数则应该落到他的有节点。而且每个结点上小球落上去的平均次数是随着层数减半的。根据这些原理就能够直接求最后一个小球的下落路径。从而减少一层循环的时间，也减少了一个表示二叉树的超大数组。

感悟：

 看来简单的题也不一定简单啊。（doge脸）

代码：

代码一：

#include<stdio.h>
#include<string.h>

using namespace std;

const int MAXN = 524288 + 100;

int tree[MAXN];

int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	int num,n, m;
	while(scanf("%d",&num) == 1 && num !=-1)
	{
		while (num--) 
		{
			scanf("%d %d",&n,&m);
			int ball;
			memset(tree, 0, sizeof(tree));
			for (int i = 0; i < m; i++)
			{
				ball = 1;
				for (int j = 1; j < n; j++)
				{
					int b = ball;
					if (tree[ball])
						ball = 2 * ball + 1;
					else
						ball = 2 * ball;
					tree[b] = !tree[b];
				}
			}
			printf("%d\n",ball);
		}
	}
	return 0;
}

代码二：

#include<iostream>

using namespace std;

int main()
{
	int num,n, m;
	while(cin >> num && num !=-1)
	{
		while (num--) 
		{
			cin >> n >> m;
			int ball = 1;
			for (int j = 1; j < n; j++)
			{
				if (m % 2)
				{
					ball = ball * 2;
					m = (m + 1) / 2;
				}
				else
				{
					ball = ball * 2 + 1;
					m = m / 2;
				}
			}
			cout << ball << endl;
		}
	}
	return 0;
}