1363：小球(drop)

【题目描述】
许多的小球一个一个的从一棵满二叉树上掉下来组成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的叶子数，写一个程序求小球停止时的叶子序号。

【输入】
一行包含两个用空格隔开的整数D和I。其中2≤D≤20，1≤I≤524288。

【输出】
对应输出第I个小球下落停止时的叶子序号。

【输入样例】
4 2
【输出样例】
12

分析

1. 可以用链式存储二叉树，也可以用数组顺序存储；然后就是模拟题上的要求，先建树，然后是I次从根节点向下走；
2. 该树是满二叉树，深度D最大为20，第1层有1个结点，第2层有2个结点，…，第D层有2^(D-1)个结点，总结点数量为 2^D-1，所以数组开到1100000；
3. 至于建树可以参考前几篇文章，小球最后落得位置，就是走到叶子结点的时候（node[u].left == 0 && node[u].right == 0），否则就改变当前的var状态，然后向左孩子或右孩子出发；
4. 参考君义大佬的：信息学奥赛一本通 1363：小球(drop)

解法一：链式存储

需要注意idx并不是图上的编号，而是根据建立结点的顺序来进行编号的，所以结构体有一个id来记录和图上一样的编号；

#include <bits/stdc++.h>using namespace std;
struct Node {bool val;int id, left, right;
};
const int N = 1100000;//2^20-1
Node node[N];
int idx;//结点编号
int D, I, ans;int createTree(int u) {int res;if (u >= pow(2, D) - 1)return 0;res = ++idx;node[res].id = u;node[res].val = false;node[res].left = createTree(2 * u);node[res].right = createTree(2 * u + 1);return res;
}void solve(int u) {if (node[u].left == 0 && node[u].right == 0) {//当前是叶子结点，也就是小球落得位置ans = node[u].id;return;}if (node[u].val == false) {node[u].val = true;solve(node[u].left);} else {node[u].val = false;solve(node[u].right);}
}int main() {cin >> D >> I;createTree(1);for (int i = 0; i < I; ++i)solve(1);cout << ans;return 0;
}

解法二：顺序存储

while循环结束，说明走到了叶子结点下一个结点，并多乘了2，或又加了个1；输出应该为出界之前的叶子结点编号，因为现在的u的值是2u或2u+1，所以需要除2；

#include <bits/stdc++.h>using namespace std;const int N = 1100000;//2^20-1
bool tree[N];
int D, I, u;int main() {cin >> D >> I;for (int i = 1; i <= I; ++i) {u = 1;//每次从根节点开始走while (1) {if (u >= pow(2, D) - 1)break;if (tree[u]) {//向右走tree[u] = false;u = u * 2 + 1;} else {tree[u] = true;u = u * 2;}}}//当前结点的上一个结点，就是叶子结点cout << u / 2;return 0;
}