UVa

UVa00712 UvaLive5665 POJ1105 OpenJ_Bailian1105 ZOJ1150 S-Trees

題目連結 UVa
題目連結 UvaLive
題目連結 POJ
題目連結 OpenJ_Bailian
題目連結 ZOJ

  • 題意：給定一顆層數為 $N+1$ 的完美二元樹，及每個葉節點的值，並告訴你在第 $i$ 層要往左還是右。問依照 $x_1,x_2,x_3,..,x_n$ 的值向左 ($x_i=0$) 或向右 ($x_i=1$)，問最終會到葉節點的值。
  • 題解：這題主要是輸入的處理要費心思。判斷最後會落在哪個點，其實就和二進位有關，如果往左走，等同二進位表示下加了 $0$，反之等同二進位表示下加了 $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
    50
    51
    52
    53
    54
    55
    56
    57
    58
    #pragma GCC optimize(2)
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <iostream>
    #include <map>
    #include <string>
    #include <vector>
    using namespace std;
    typedef unsigned long long ULL;
    const int INF = 1e9;
    const int MXN = 1e5 + 5;
    const int MXV = 3e5 + 5;
    const ULL MOD = 10009;
    const ULL seed = 31;
    #define MP make_pair
    #define PB push_back
    #define F first
    #define S second
    #define FOR(i, L, R) for (int i = L; i != (int)R; ++i)
    #define FORD(i, L, R) for (int i = L; i != (int)R; --i)
    #define IOS                                                                    \
        cin.tie(NULL);                                                             \
        cout.tie(NULL);                                                            \
        ios_base::sync_with_stdio(false);
    int main()
    {
        int n, m, ti = 0;
        vector<int> order;
        string s, r;
        while (cin >> n, n)
        {
            order.resize(n);
            char ch;
            FOR(i, 0, n) { cin >> ch >> order[i]; }
            cin >> s;
            cout << "S-Tree #" << ++ti << ":\n";
            cin >> m;
            FOR(i, 0, m)
            {
                cin >> r;
                int x = 0;
                FOR(j, 0, n)
                {
                    if (r[order[j] - 1] == '0')
                    {
                        x = 2 * x;
                    }
                    else
                    {
                        x = 2 * x + 1;
                    }
                }
                cout << s[x];
            }
            cout << "\n\n";
        }
    }

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Recommended Posts