POJ

POJ2499 Binary Tree

題目連結

  • 題意：一顆二元樹，樹根為 $(1,1)$，如果節點為 $(a,b)$，他的左子節點為 $(a+b,b)$，右子節點為 $(a,a+b)$，給定一個節點 $(x,y)$，求根走到此點，向左和向右各多少次。
  • 題解：從 $(x,y)$ 往回推，假設 $x>y$ 且 $x=ky+y%x$，那麼 $(x,y)$ 是由 $(y%x,y)$ 往左 $k$ 次到達，$y>x$ 的情況相似。因此，可以利用除法來計算出到底往左和往右走了幾步。
    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
    59
    60
    #pragma GCC optimize(2)
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <iostream>
    #include <map>
    #include <string>
    #include <vector>
    using namespace std;
    typedef long long LL;
    const int INF = 1e9;
    const int MXN = 1e5 + 5;
    const int MXV = 3e5 + 5;
    const LL MOD = 10009;
    const LL 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 t = 0;
        cin >> t;
        FOR(ti, 1, t + 1)
        {
            LL i, j;
            cin >> i >> j;
            int ansL = 0, ansR = 0;
            while (i != 1 || j != 1)
            {
                // cout << i << ' ' << j << '\n';
                if (i == 1 || j == 1)
                {
                    ansL += i - 1;
                    ansR += j - 1;
                    break;
                }
                if (i < j)
                {
                    ansR += (j - j % i) / i;
                    j %= i;
                }
                else
                {
                    ansL += (i - i % j) / j;
                    i %= j;
                }
                // cout << ansL << ' ' << ansR << "\n";
            }
            cout << "Scenario #" << ti << ":\n";
            cout << ansL << ' ' << ansR << "\n\n";
        }
    }

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

Recommended Posts