【UVA679】Dropping Balls 解题报告

题目链接：点击打开链接

是一个二叉树的编号，首先想到要最后一个球，那我就模拟从第一个球开始，走过的改变状态：要么从关闭（0）变为开启（1），要么从开启（1）变为关闭（0）。用一个数组保存结点状态。

代码如下：

 

#include<bits/stdc++.h>
using namespace std;

const int maxd = 20;
int s[1<<maxd];
int main(){
	
	int l;
	while(scanf("%d",&l)){
		if(l == -1)
			break;
			 
		while(l--){			
			memset(s,0,sizeof(s));
			int D,I;
			scanf("%d %d",&D,&I);
			int n = (1<<D)-1; //最大结点 
			int k = 1;   //每次的结点 
			
			for(int i = 0;i < I;i++)// 
			{	
				k = 1; 
				while(1)
				{
					s[k] = !s[k]; //经过的点改变，不然先变k，就相当于改下一点的状态 
					if(s[k])
						k = 2*k;
					else
						k = 2*k+1;
					if(k > n) 
						break;
				}
				
					
			}
			printf("%d\n",k/2);
			
		}
	} 
	return 0;
} 

然后编写完成，兴高采烈的去Submit，结果显示：Time Limit Exceeded
原来是每次输入，都要把所有点跑一次，而I的可以最大到2^D-1

 

这样子就一个数据就要高达(2^20)*20，而输入数据最多为1000组。而一般1s的操作4*（10^8）。这样子就TLE了。

 

分析可以发现，每次到一个节点，奇数点（状态为0）往左边走，偶数点往右边走。

而到下一层同样的道理，所以每次就判断最后一个球的奇偶性即可。

比如上一层的1,3,5,7,9都会往左边走到下一层，而下一层又要从1,2,3,4,5这样子，所以1/2+1, 3/2+1, 5/2+1…，所以奇数往左边走的，就 I = I/2+1。然后再继续判断奇偶性。

而原本上一层是偶数的，2,4,6,8,10会往右边走到下一层，而下一层又要从1,2,3,4,5这样子，所以2/2, 4/2, 6/2…，所以奇数往右边走的，就 I = I/2。然后再继续判断奇偶性。

所以每次的输入，就直接考虑最后一个球I即可。只要走到最后一层D。这样子每次数据处理只用最多20，就不会TLE了。

代码如下：

 

#include<bits/stdc++.h>
using namespace std;

int main(){
	
	int l;
	while(scanf("%d",&l)){
		if(l == -1)
			break;
			 
		while(l--){			
			int D,I;
			scanf("%d %d",&D,&I);
			
			//**改进代码**// 
			//由于每个球，先进左子树，下一个就进右子树，按奇偶性判断 
			for(int i = 0;i < D-1;i++)
			{
				if(I%2)
				{
					k = k*2;
					I = I/2+1;
				}
				else
				{
					k = k*2+1;
					I /= 2; 
				}
			}
		
			printf("%d\n",k);
			
		}
	} 
	return 0;
} 

最后去提交，发现AC了。万岁！！！！！