原题链接：小球下落 Dropping Balls - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
刚开始学习数据结构中的树。看到这题时第一想法肯定时暴力模拟，由于题目条件给出 1<I<600000,所以最大运算量约为20*6e5=1.2e6.好像也能解（这里就不给出代码了）。
但是更进一步思考，会发现当一个小球落在一个结点位置时，会根据其是落在该结点的第几个来判断其是落在左子树还是右子树。那么那么我们就不用再模拟前 I-1 次了，可以直接对第I个小球进行模拟，即奇数落在左子树，偶数落在右子树，然后进行除二操作。
主要代码：
#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; while (n--){ int D,I,node=1; cin>>D>>I; //输入深度和第几个小球 for (int i=0;i<D-1;i++){ if (I%2==0) {I=I/2;node=node*2+1;} //偶数，落在右子树 else {I=(I+1)/2;node*=2;} //奇数，落在左子树 } printf("%d\n",node); } cin>>n; return 0; }
ps：这题只是简单的运用了树中儿子结点和父亲结点的对应关系