【UVA-679】解题报告（二叉树）

原始题目

题目大意

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

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

解题思路

  • 考虑根节点，发现奇数次序小球向左下，偶数小球向右。
  • 同理，若为\(I\)奇数，则其是到达左子树的第$ \(个小球，序号为\) 2 index $。
  • 若位偶数，则其是到达右子树的第$ $个小球，序号为 $ 2 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;
    }

收获与反思

  • 注意奇偶性规律