暑假集训——个人训练赛04——F题

模拟题

题意：一棵高度为h的树，每次你只能按左右左右的方向去走（你走左边后你就得走右边），然后在树的最底下有2^h个点，问走到第n个点时所走过的所有点的个数。

思路：如果你实际走的方向和你需要走的方向相反的话，那么你需要走完这一棵子树上的所有点，如果相同的话，那么你只要加上你走过的这一个点。

#include<stdio.h>

int main()
{
	__int64 h,n;
	while(~scanf("%I64d%I64d",&h,&n))
	{
		__int64 ans=0;
		int flag=0;//0表示左边，1表示右边
		for(int i=0;i<h;i++)
		{
			__int64 t=1LL<<(h-i-1);//这个需要自己模拟计算一遍，不然怎么叫模拟题呢？
			if(n>t&&flag==0)//需要走的在右边，而实际走的在左边
			{
				ans+=1LL<<(h-i);
				n-=t;
			}
			else if(n>t&&flag==1)//需要走的在右边，而实际走的也在右边
			{
				ans+=1;
				flag=0;//正确走后，走的方向需要改变
				n-=t;
			}
			else if(n<=t&&flag==0)//需要走的在左边，而实际走的也在左边
			{
				ans+=1;
				flag=1;//正确走后，走的方向需要改变
			}
			else if(n<=t&&flag==1)//需要走的在左边，而实际走的在右边
			{
				ans+=1LL<<(h-i);
			}
		}
		printf("%I64d\n",ans);
	}
	return 0;
}