UVA 679 Dropping Balls(二叉樹性質）

​​Dropping Balls​​

題意，有一顆完全二叉樹，有好多球從根節點往下走，關于往左還是往右要看每個節點的開關，初始的話全部關閉，每走過一個節點，這個節點開關會改變一次，問最後一個球落在哪個葉子節點，給出編号（開關開往右，反之往左）

這裡有幾個知識點

1.寫法等同與 n * 2m

2. 因為

優先級比

高，是以n * 2m+1要寫為(n << m) + 1

3. 對于完全二叉樹，每個節點

的左右節點為

第一眼看的話很容易寫出模拟版本的，模拟每一個小球，但是會逾時

#include<bits/stdc++.h>
using namespace std;
const int N = 20;

int _, n, m;
int a[1<<N];    //1<<N即為1*2^n
          //最大節點數為2^n-1
int main()
{
  for (scanf("%d", &_); _; _--){
    cin >> n >> m;
    int maxn = (1 << n) - 1;      //最大節點數
    // cout << maxn << endl;
    memset(a, 0, sizeof(a));    //開關剛開始的時候為關閉，0
    int start;
    for(int i = 0; i < m; i++){    //連續讓m個小球下落
      start = 1;
      while(start <= maxn){      //落出界後退出
        start = a[start] ? (start << 1) + 1 : start << 1; //選擇方向
        a[start>>1] = !a[start>>1];             //改變開關
      }
    }
    // cout << start << endl;
    cout << (start >> 1) << endl; //輸出節點start/2
  }
  cin >> _;
  return 0;
}      

仔細思考下就會發現，對于每一個節點隻要知道目前小球是第奇數個還是偶數個到達這個節點的，就可以判斷往左走還是右。

• 1 >>>> 左
• 2 >>>> 右
• 3 >>>> 左
• … …

知道往左還是往右，就推出來是第幾個到達子樹了

• 第D次到達父節點
• 往左 >>>> 第
• 次到達左子樹
• 往右 >>>> 第
• 次到達右子樹

那麼我們就可以直接模拟最後的小球的路徑了

#include<bits/stdc++.h>
using namespace std;
const int N = 20;

int _, n, m;
int main()
{
  for (scanf("%d", &_); _;_--){
    cin >> n >> m;
    int ans = 1;        //節點的編号
    for(int i = 0; i < n-1; i++){  //小球下降了n-1次，
                    //第m個小球是第m個到達1節點的
      if(m&1){        //n為奇數
        ans = ans << 1;   //往左
        m = (m + 1) / 2;  //最後一個小球到達左子樹是第幾個到達的
      }else{  
        ans = (ans << 1) + 1; //往右
        m = m / 2;      //最後一個小球到達右子樹是第幾個到達的
      }
    }
    cout << ans << endl;
  }
  cin >> n;
  return 0;
}