UVa

UVa11362 POJ3630 HDU1671 ZOJ2876 SPOJ-PHONELST OpenJ_Bailian3791 Codeforces100240A SCU1341 Kattis-phonelist LibreOJ10049 Phone List

題目連結 UVa
題目連結 POJ
題目連結 HDU
題目連結 ZOJ
題目連結 SPOJ
題目連結 OpenJ_Bailian
題目連結 Codeforces
題目連結 SCU
題目連結 Kattis
題目連結 LibreOJ

  • 題意：給定一本電話簿有多個電話號碼，問這些電話號碼是否合法。合法定義為對於任兩組電話，互不為對話的前綴。
  • 題解：用 trie 紀錄每一種字串，是多少字串的前綴，接著搜尋答案時，如果發現該字串為別人的前綴時，就得知這本電話簿不合法。
  • 心得：EOlymp2303 和 OpenJ_Bailian4089 無法通過。
    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
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    #pragma GCC optimize(2)
    #include <algorithm>
    #include <bitset>
    #include <cmath>
    #include <cstring>
    #include <iostream>
    #include <map>
    #include <queue>
    #include <set>
    #include <stack>
    #include <string>
    #include <vector>
    using namespace std;
    typedef pair<int, int> PII;
    typedef long long LL;
    const int INF = 1e9;
    const int MXN = 1e5 + 5;
    const int MXV = 1e5 + 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);
    bool ok;

    struct Node
    {
        int i;
        char ch;
        int v;
        Node *next[10];
        void init(char _ch = '\0')
        {
            v = 0;
            FOR(i, 0, 10) next[i] = NULL;
        }
        Node() { init(); }
    } node[MXN];
    int nodei;
    char s[MXN][15];

    void insert(Node *root, string s)
    {
        FOR(i, 0, s.size())
        {
            int v = s[i] - '0';
            if (root->next[v] == NULL)
            {
                root->next[v] = &node[++nodei];
                root->next[v]->init();
            }
            root = root->next[v];
            root->ch = s[i];
            ++root->v;
        }
        return;
    }

    void search(Node *root, string s)
    {
        FOR(i, 0, s.size())
        {
            int v = s[i] - '0';
            root = root->next[v];
        }
        if (root->v > 1)
        {
            ok = false;
        }
    }

    int main()
    {
        FOR(i, 0, MXN) { node[i].i = i; }
        int t;
        scanf("%d", &t);
        while (t--)
        {
            int n;
            Node *root = &node[0];
            scanf("%d", &n);
            root->init();
            nodei = 0;
            FOR(i, 0, n)
            {
                scanf("%s", s[i]);
                insert(root, s[i]);
            }
            ok = true;
            FOR(i, 0, n)
            {
                search(root, s[i]);
                if (!ok)
                {
                    break;
                }
            }
            if (ok)
            {
                printf("YES\n");
            }
            else
            {
                printf("NO\n");
            }
        }
    }

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

Recommended Posts