【UVA-679】解题报告(二叉树)

原始题目

题目大意

一颗完全二叉树(FBT)初始所有结点标记为false,根结点标号1,对于一个小球从根结点释放,
遇到false标记向左下,true标记向右下,直至到达叶子结点。每次经过标记后标记翻转。

给出完全二叉树(FBT)的深度$D$,和小球的次序$I$,求其最终下落的叶子节点标号。

解题思路

  • 考虑根节点,发现奇数次序小球向左下,偶数小球向右。
  • 同理,若为$I$奇数,则其是到达左子树的第$ \frac {I+1}{2}$个小球,序号为$ 2 \times index $。
  • 若位偶数,则其是到达右子树的第$ \frac {I}{2} $个小球,序号为 $ 2 \times index + 1 $。
  • 递推n-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
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    #include <cstdio>
    #include <iostream>
    #include <iomanip>
    #include <vector>
    #include <string>
    #include <cstring>
    #define rep(i,a,n) for(int i=a;i<n;++i)
    #define per(i,a,n) for(int i=n-1;i>=a;--i)
    #define clint(x,a) memset(x,a,sizeof(int)*n)
    #define clll(x,a) memset(x,a,sizeof(ll)*n)
    #define pb push_back
    #define np next_permutation
    #define mp make_pair
    #define fi first
    #define se second
    #define INF 0x3f3f3f3f
    #define EPS 1e-8
    #define PI acos(-1.0)
    using namespace std;
    const int maxn=1e5+5;
    const int maxm=1e5+5;
    const int maxl=26;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef vector<int> vi;
    typedef pair<int,int> pii;
    typedef pair<string,string> pss;

    ll t,d,ii;
    int main(){
    ios::sync_with_stdio(false);
    cin>>t;
    rep(tt,1,t+1){
    cin>>d>>ii;
    ll ans=1;
    for(int i=1;i<d;i++){
    if(ii&1){
    ans*=2;
    ii=(ii+1)/2;
    }
    else{
    ans=ans*2+1;
    ii=ii/2;
    }
    }
    cout<<ans<<endl;
    }
    cin>>t;
    }

收获与反思

  • 注意奇偶性规律