看到這題一開始的想法就是直接模擬一棵完全二叉樹，然后根據(jù)每一層的開關(guān)值來決定小球向左走還是向右走蹬碧。
需要注意的是瑟慈，若完全二叉樹根節(jié)點編號為1航唆，則編號為n的結(jié)點的左孩子的標(biāo)號為2n将谊，右孩子的標(biāo)號為2n+1。
然而渐白。尊浓。這題直接模擬會超時。纯衍。于是百度之后發(fā)現(xiàn)了一種直接根據(jù)小球的奇偶性來判斷它往哪邊落的方法栋齿，還是挺強(qiáng)的。襟诸。(結(jié)果做完才發(fā)現(xiàn)書上后面也講了會超時瓦堵。。手動再見歌亲。菇用。)
直接模擬TLE代碼如下：
#include <cstdio>
#include <cstring>
const int maxd = 20;
bool flag[1 << maxd];
int main() {
int l, D, I;
scanf("%d", &l);
while ((scanf("%d %d", &D, &I)) == 2) {
memset(flag, false, sizeof(flag));
int last = 0;
for (int i = 0; i < I; i++) {
int index = 1, depth = 1;
while (depth != D) {
if (!flag[index]) {
flag[index] = true;
index = 2 * index;
}
else {
flag[index] = false;
index = 2 * index + 1;
}
depth++;
}
if (i == I - 1) last = index;
}
printf("%d\n", last);
}
}
另一種思路時，對于樹中每一個結(jié)點陷揪，只要知道當(dāng)前小球是第幾個到達(dá)該結(jié)點的小球惋鸥，就能知道它下一步是往左走還是往右走，因為開關(guān)每次都會反轉(zhuǎn)一下悍缠。這樣的話就根本不用模擬出二叉樹并且每一個小球都落一遍了卦绣，很省時間。
以根結(jié)點為例飞蚓，當(dāng)I為奇數(shù)滤港，即第奇數(shù)個小球放在根結(jié)點時，小球一定是落向左子樹趴拧，而I為偶數(shù)時則落向右子樹溅漾。之后只需要確定該小球?qū)τ谧笞訕浠蛘哂易訕涞母Y(jié)點是第幾個小球，就能完成整個迭代過程八堡。
經(jīng)找規(guī)律可知樟凄，對于根結(jié)點的第I個球聘芜，若I為奇數(shù)兄渺，則它對于根的左子樹的根結(jié)點是第(I+1)/2個小球，若I為偶數(shù)汰现，則它對于根的右子樹的根結(jié)點是第I/2個小球挂谍。接下來只要繼續(xù)判斷(I+1)/2或I/2的奇偶性，就能知道小球在子樹上是往左走還是往右走了瞎饲。
一個自我感覺是口叙，對于完全二叉樹，只需要考慮根和左子樹嗅战、右子樹之間的規(guī)律妄田，對于剩下的每一層俺亮，規(guī)律都是一樣的，因為二叉樹是遞歸定義的疟呐。
AC代碼如下：
#include <cstdio>
#include <cstring>
int main() {
int l, D, I;
scanf("%d", &l);
while ((scanf("%d %d", &D, &I)) == 2) {
int k = 1;
for (int i = 0; i < D - 1; i++) {
if (I % 2 == 1) {
k = 2 * k;
I = (I + 1) / 2; // 當(dāng)I是奇數(shù)時脚曾，它是往左走的第(I+1)/2個小球
}
else {
k = 2 * k + 1;
I = I / 2; // 當(dāng)I是偶數(shù)時，它是往右走的第I/2個小球
}
}
printf("%d\n", k);
}
}
