题目：Dropping Balls
题意：有一颗深度为d的二叉树，i个小球从根节点向下落。每个节点上有一个开关，小球落在该节点上时，若开关为开则向右走；反之向左走。小球每经过一次开关，开关的状态改变一次。求第i个小球最终会落到哪个节点上。
思路：
1、模拟。定义一个数组bool a，用来存储开关情况。小球当前位置为k时，像左走为2*k，像右走为2*k+1。（TLE）
2、因为小球的下落是有规律的，假如第j个小球向左，那么j+1个小球一定会向右走。所以只关心最后一个小球的奇偶性即可。
注意：思路2中，如果忘记删除思路1中的a数组的初始化，会超时。
TLE代码：
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<deque>
using namespace std;int l,d,s;
bool a[(1<<20)]={0};int main() {scanf("%d",&l);while(l--){memset(a,0,sizeof(a));scanf("%d%d",&d,&s);int n=(1<<d)-1;int where=1;for(int i=1;i<=s;i++){where=1;do{if(a[where]==false) where*=2;else where=where*2+1;a[where/2]^=1;}while(where<=n);}printf("%d\n",where/2);}return 0;
}
AC代码：
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<deque>
using namespace std;int l,d,s;int main() {scanf("%d",&l);while(l--){scanf("%d%d",&d,&s);int where=1;do{if(s%2==0){where=where*2+1;s/=2;}else{where*=2;s=(s+1)/2;}d--;}while(d>=2);printf("%d\n",where);}return 0;
}