这道题显然可以直接模拟前 \(I\) 个小球的掉落,最终即可得解.但是,很明显,这么做会使时间复杂度直接爆炸成 \(O(l\times D\times I)\),已然是力不从心.
仔细观察,可以简单地发现:我们只需模拟第 \(I\) 个小球的运动即可,通过判断当前节点上已经经过了的小球数的奇偶性,可以轻松判断第 \(I\) 个小球的运动路线(这句话是整道题解题方法的精髓,请仔细理解后看下面的代码).
Code:
#include <bits/stdc++.h>
using namespace std;
int l,D,I;
void rd(int&);
void wt(int);
int main() {
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
rd(l);
while (l--) {
rd(D),rd(I);
int node=1,total=(1<<D)-1;
for (;;) {
I&1?(node<<=1,I=I+1>>1):(node=node<<1|1,I>>=1);
if (node>total) {
wt(node>>1);
putchar('\n');
break;
}
}
}
return 0;
}
void rd(int& x) {
x=0;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch)) {
x=x*10+ch-48;
ch=getchar();
}
}
void wt(int x) {
if (x>9)
wt(x/10);
putchar(x%10+48);
}