【題目描述】

許多的小球一個一個的從一棵滿二叉樹上掉下來組成FBT（Full Binary Tree，滿二叉樹），每一時間，一個正在下降的球第一個訪問的是非葉子節(jié)點。然后繼續(xù)下降時，或者走右子樹，或者走左子樹，直到訪問到葉子節(jié)點。決定球運動方向的是每個節(jié)點的布爾值。最初，所有的節(jié)點都是false，當訪問到一個節(jié)點時，如果這個節(jié)點是false，則這個球把它變成true，然后從左子樹走，繼續(xù)它的旅程。如果節(jié)點是true，則球也會改變它為false，而接下來從右子樹走。滿二叉樹的標記方法如下圖:

因為所有的節(jié)點最初為false，所以第一個球將會訪問節(jié)點1，節(jié)點2和節(jié)點4，轉變節(jié)點的布爾值后在在節(jié)點8停止。第二個球將會訪問節(jié)點1、3、6,在節(jié)點12停止。明顯地，第三個球在它停止之前，會訪問節(jié)點1、2、5，在節(jié)點10停止。

現在你的任務是，給定FBT的深度D，和I，表示第I個小球下落，你可以假定I不超過給定的FBT的葉子數，寫一個程序求小球停止時的葉子序號。

【輸入】

一行包含兩個用空格隔開的整數D和I。其中2≤D≤20，1≤I≤524288。

【輸出】

對應輸出第I個小球下落停止時的葉子序號。

【輸入樣例】

4 2

【輸出樣例】

12

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 1000001 #define MOD 123 #define E 1e-6 using namespace std; int D,I; int b[N]; int ans; void down(int k) {if( pow(2,(D-1))<=k && k<pow(2,D) ){ans=k;return;}if(b[k]){b[k]=!b[k];down(2*k+1);}else{b[k]=!b[k];down(2*k);} } int main() {int i,a;cin>>D>>I;for(i=1;i<=I;i++)down(1);cout<<ans<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的小球（信息学奥赛一本通-T1363）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。