POJ

POJ1785 Binary Search Heap Construction

題目連結

  • 題意：給定 $N$ 顆節點，要構出笛卡爾樹並中序輸出
  • 題解：笛卡爾樹是一顆符合樹性質和根性質的樹，Treap 也是一種笛卡兒樹，職不過 Treap 的 val 是隨機的。要構造一顆笛卡爾樹，先將節點依 key 值排序，依序插入樹中，每顆節點依開始在樹的最右邊，往父親方向，找出第一個 key > 當前節點 key 的祖先 $P$，將 $P$ 的右子節點設為當前節點，$P$ 原本的右子節點設為當前節點的左子樹。
  • 參考：https://oi-wiki.org/ds/cartesian-tree/#treap
    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
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    #pragma GCC optimize(2)
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <iomanip>
    #include <iostream>
    #include <map>
    #include <string>
    #include <vector>

    using namespace std;
    typedef long long LL;
    const int INF = 1e9;
    const int MXN = 5e4 + 5;
    const int MXS = 1e2 + 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);
    char s[MXN][MXS];
    struct Node
    {
        int key, val;
        int Lc, Rc, p;
        bool operator<(const Node &rhs) const
        {
            return strcmp(s[key], s[rhs.key]) < 0;
        }
    } node[MXN];

    void insert(int x)
    {
        int y = x - 1;
        while (node[y].val < node[x].val)
        {
            y = node[y].p;
        }
        node[x].Lc = node[y].Rc;
        node[node[x].Lc].p = x;
        node[y].Rc = x;
        node[x].p = y;
    }

    void dfs(int x)
    {
        if (x == 0)
        {
            return;
        }
        printf("(");
        dfs(node[x].Lc);
        printf("%s/%d", s[node[x].key], node[x].val);
        dfs(node[x].Rc);
        printf(")");
    }

    int main()
    {
        int n;
        while (scanf("%d", &n), n)
        {
            FOR(i, 1, n + 1)
            {
                scanf(" %[a-z]/%d", s[i], &node[i].val);
                node[i].key = i;
                // printf("%s-%d\n", s[i], node[i].val);
            }
            sort(node + 1, node + n + 1);
            node[0].val = INF;
            node[0].Lc = node[0].Rc = node[0].p = 0;
            FOR(i, 0, n + 1)
            {
                node[i].Lc = node[i].Rc = node[i].p = 0;
                insert(i);
            }
            dfs(node[0].Rc);
            printf("\n");
        }
    }

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

Recommended Posts