信息学奥赛一本通小球（drop）

本文主要是介绍信息学奥赛一本通小球（drop），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2018年信息学奥赛NOIP资料下载
This drop is gonna last forever！

许多的小球一个一个的从一棵满二叉树上掉下来组成FBT（Full Binary Tree，满二叉树），每一时间，一个正在下降的球第一个访问的是非叶子节点。然后继续下降时，或者走右子树，或者走左子树，直到访问到叶子节点。决定球运动方向的是每个节点的布尔值。最初，所有的节点都是false，当访问到一个节点时，如果这个节点是false，则这个球把它变成true，然后从左子树走，继续它的旅程。如果节点是true，则球也会改变它为false，而接下来从右子树走。满二叉树的标记方法如下图:

因为所有的节点最初为false，所以第一个球将会访问节点1，节点2和节点4，转变节点的布尔值后在在节点8停止。第二个球将会访问节点1、3、6,在节点12停止。明显地，第三个球在它停止之前，会访问节点1、2、5，在节点10停止。

现在你的任务是，给定FBT的深度D，和I，表示第I个小球下落，你可以假定I不超过给定的FBT的叶子数，写一个程序求小球停止时的叶子序号

——以上是题目；
当第一次看到这道题的时候，好像是11月11日（巧了），刚刚自己学习了建树的蒟蒻的我马上想到了去模拟这个过程。原理很简单，用指针去建树，然后每个结构体内去维护四个变量：

1、bool check ---- 判断是否往左还是往右； 2、int data ---- 记录该结点的值；

3、node *lchild ---- 指向左儿子的指针； 4、node *rchild ---- 指向右儿子的指针；

#include<bits/stdc++.h>
using namespace std;
typedef struct node;
typedef node tree;
struct node{
char data;
bool check;
tree lchild,rchild;
};
tree root;
char c;
int D;
long long num, I, ans, i;
void build_bt(tree &bt,int sum,int num){
if(sum>D){
return;
}
bt=new node;
bt->data=num;
bt->check=false;
build_bt(bt->lchild,sum+1,num2);
build_bt(bt->rchild,sum+1,num*2+1);
}
int solve(int depth,tree &bt){
if(depth==D)
return bt->data;
if(bt->check){
bt->check=false;
solve(depth+1,bt->rchild);
}
else{
bt->check=true;
solve(depth+1,bt->lchild);
}
}
int main(){
cin>>D>>I;
build_bt(root,1,1);
for(i=1;i<=I;i++){
ans=solve(1,root);
}
cout<<ans;
return 0;
}
只要建了树，一遍一遍跑就是了，扪心一想：嗯，一定是将会AC了；

信心满满提交然而并没有AC，WA！没有爆内存，也没有超时，就是WA，GG（挠头）。

改了很久都还是WA，心中mmp骂不出来，于是尝试用数组去做：利用二叉树的左右儿子编号分别为为父亲编号2和父亲编号2+1，构建一个数组去模拟，还是开bool数组去判断掉到左边还是右边；

#include<bits/stdc++.h>
using namespace std;
int tr[1<<20];
long long I,D,ans;
long long tree_doit(){
int node=1;
for(int i=1;i<=D-1;i++){
if(!tr[node]){
tr[node]=1;
node=node2;
}
else{
tr[node]=0;
node=node2+1;
}
}
return node;
}
int main(){
cin>>D>>I;
for(int i=1;i<=I;i++)
ans=tree_doit();
cout<<ans;
return 0;
}
是AC掉了没错，但还是觉得不对，一定有规律可循，想啊想，豁然开朗（噗）。

不难发现我们所需要求的是最后一个小球的位置，那我们可不可以只去模拟最后一个小球的掉落呢？

有人会问：你怎么知道球会怎么落呐？难道不是需要去求出前 I-1 个球所改变的方向吗？

但我们根本不需要知道。

首先球在第一层只会落两个方向：左，右；说明我们球落到球要么在一边，要么在另一边，所以 I 个球落下会在剩下一个球或0

个时，左右是”均分“的。

由于球是先从左边开始落的，落下奇数个球一定是落在左边的，偶数个一定是落在右边的。可以类比一下走路，假如您迈出的第一步是左脚，那么走奇数步时正在迈出的一定是左脚，而不是右脚。

（假如题目改一下，小球先从右边落，在从左落下，道理也是一样的！）

这只是第一层，第二层，第三层 …… 第D层呢？

我们可以发现，无论是在哪一层，小球都需要用一半（[I/2]（向下取整））个小球去克服两边的每一边，最后的那个球，和第一层一样，只是球的总数变成了原来的1/2；

但是不是左右两边都会剩下一半呢？不是，左边会多剩下一个，还是那个道理，左脚先迈出，左脚便有”先决优势“。

还是利用那个父与子的编号性质，左掉编号2，右掉编号2+1。

好啦，放代码：

#include<bits/stdc++.h>
using namespace std;
int ans=1,D,I;
int main(){
cin>>D>>I;
for(int i=2;i<=D;i++)
if(I%2==1){
ans*=2;
I=I/2+1;
}
else{
ans=ans*2+1;
I/=2;
}
cout<<ans;
return 0;
}
嗯，AC，而且代码显然剪短了许多。
但是我还是不明白为什么建树不对，好歹代码也是这么长的啊。