#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
using namespace std;
const int maxn = 20;
const int record = 1 << maxn;
int s[record];//记录开关的状态
int main()
{
int t;
while (1)
{
cin >> t;
if (t == -1)
break;
int d, i;
while (t--)
{
cin >> d >> i;//d代表深度，i代表询问的第i个球
memset(s, 0, sizeof(s));
int k, n = (1 << d) - 1;//n记录最大叶子结点的编号
for (int j = 0; j < i; j++)//有i个球，进行i次的尝试
{
k = 1;
for (;;)
{
s[k] = !s[k];//球经过后会发生相应状态的改变
k = s[k] ? k * 2 : k * 2 + 1;//注意细节，是球经过后相应开关状态发生改变，赋值应相反
if (k > n)
break;
}
}
printf("%d\n",k / 2);//越界前的数输出
}
}
getchar();
getchar();
return 0;
}
第一种方法直接模拟，数据最多有1000组，并且以k>n进行跳出循环的判断，2的19次方乘19，必然超时
1、此题重要思想，注意二叉树的编号中，左右节点与根节点存在重要关系，若根节点为k，则左节点为2*k，右节点为2*k+1
2、每个小球必定会到达根节点，所以通过是第几个经过该节点的球可以判断是向左还是向右，用奇偶控制，因为初始为关，奇数则代表关，偶数则代表开
3、直接模拟最后一个球行走的路径即可
4、此题一定注意理解根节点与左右节点之间的关系， 建立寻找两者关系
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
using namespace std;
int main()
{
int t;
while (1)
{
cin >> t;
if (t == -1)
break;
while (t--)
{
int d, i;
cin >> d >> i;
int k = 1;
for (int j = 0; j < d - 1; j++)//以深度模拟最后一个球的轨迹
{
if (i % 2)//为奇数的情况
{
k = 2 * k;
i = (i + 1) / 2;
}
else
{
k = 2 * k + 1;
i = i / 2;
}
}
printf("%d\n", k);
}
}
getchar();
getchar();
return 0;
}
