題目簡述

  • 有一個滿二元樹,題目會多次的從樹根放球往下掉
  • 每個節點都有一個標記,一開始初始值是往左,當有一顆球經過時,就會切換成右,再有一顆球經過,就切換成左,以此類推
  • 當一顆球來到一個節點,依照標記來決定要往左子樹走,還是右子樹走,來走到下一層
  • 一顆球走到最下面那層,就會有最後停下來的那個節點編號,然後就可以從樹根放下一顆球
  • 題目會給定最大深度 $D$ 和總共放了 $I$ 顆球
  • 輸出第 $I$ 顆球最後會停在哪個節點

    解題想法

  • 可以開一個陣列存二元樹,然後依序模擬每一顆球往下掉的過程和結果,最後輸出答案,不過這樣可能會 TLE
  • 若是可以給定第 $I$ 顆球,直接計算就會快很多
  • 想法
    1. 若是數字是奇數,那應該往左走,若是偶數則往右走
    2. 每往下走一層,數字應該要除以二
  • 所以就用一個 for 迴圈掃過每一層,然後每一層決定要往左走還是往右走
  • 注意若此節點編號為 $N$,則下一層左邊節點編號為 $2N$,右邊節點編號為 $2N+1$

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*****************************************
Filename:p679.cpp
Author:Willy Chen(willychen.org)
Date:2019.09.30
*****************************************/
#include<iostream>
using namespace std;

int main(){
int kase;
cin >> kase;
while(kase--){
int D, I;
cin >> D >> I;
int now = 1, remain = I;
for(int i = 1; i < D; ++i){
if(remain % 2 == 1){
// Left
now = 2 * now;
remain = (remain + 1) / 2;
}else{
// Right
now = 2 * now + 1;
remain = remain / 2;
}
}
cout << now << endl;
}
return 0;
}

評論

 無法加載Disqus評論系統,請確保您的網絡能夠正常訪問。



本站使用 Volantis 作為主題