【专题训练】 —字典树【11/16】

发表于 | 更新于 | 分类于

专题链接：

https://vjudge.net/contest/50484

A - Shortest Prefixes POJ - 2001 【Easy】

题目大意：

将给出的所有单词通过取其前缀来代替此单词进行“简化”，使“简化”后的单词能唯一标识这个单词，在这前提下找到最简的化简结果。
例如，给出car、cart、carton“简化”后的单词分别为car、cart、carto。

解题思路：

建立字典树，对于每个要“化简”的单词，我们找到那个到此位置处前缀只有这一种情况的结点，然后输出这条路径上的字符就是要找的最简结果。

Mycode：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 1010;
const int MAXL = 1010 * 20;

string tem;
char s[MAXN][22];
struct Tire
{
    int nex[MAXL][26], tot, pre[MAXL];
    void init()
    {
        tot = 1;
        memset(nex, 0, sizeof(nex));
        memset(pre, 0, sizeof(pre));
    }
    void add(char *str)
    {
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            if(!nex[now][str[i]-'a'])
                nex[now][str[i]-'a'] = ++tot;
            now = nex[now][str[i]-'a'];
            pre[now]++;
        }
    }
    /*int Find(const char *str)
    {
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            if(!nex[now][str[i]-'a'])
                return 0;
            now = nex[now][str[i]-'a'];
        }
        return now;
    }*/
    void print(char *str)
    {
        printf("%s ", str);
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            now = nex[now][str[i]-'a'];
            printf("%c", str[i]);
            if(pre[now] == 1)   break;
        }
        puts("");
    }
}tire;
int main()
{
    tire.init();
    int n;
    for(n = 1; ~scanf("%s", s[n]); ++n)
    {
        tire.add(s[n]);
    }
    for(int i = 1; i < n; ++i)
    {
        tire.print(s[i]);
    }
    return 0;
}

B - T9 POJ - 1451

题目大意：

解题思路：

Mycode：

1
2


C - Wild Words POJ - 1816

题目大意：

解题思路：

Mycode：

1
2


D - Phone List POJ - 3630 【Easy】

题目大意：

判断是否有前缀。

解题思路：

建树直接判。

Mycode：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX = 1e5 + 5;

struct Tire
{
    int tot, nex[MAX][11], pre[MAX], cnt[MAX];
    void init()
    {
        tot = 1;
        memset(nex, 0, sizeof(nex));
        memset(pre, 0, sizeof(pre));
//        memset(cnt, 0, sizeof(cnt));
    }
    void add(char *str)
    {
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            if(!nex[now][str[i]-'0'])
                nex[now][str[i]-'0'] = ++tot;
            now = nex[now][str[i]-'0'];
            pre[now]++;
        }
//        cnt[now]++;
    }
    int Find(char *str)
    {
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            if(!nex[now][str[i]-'0'])
                return 0;
            now = nex[now][str[i]-'0'];
        }
        return pre[now];
    }
}tire;
int main()
{
    int t, n;
    char s[MAX][11];
    scanf("%d",&t);
    while(t--)
    {
        tire.init();
        scanf("%d",&n);
        for(int i = 0; i < n; ++i)
        {
            scanf("%s", s[i]);
            tire.add(s[i]);
        }
        bool flag = true;
        for(int i = 0; i < n && flag; ++i)
        {
            if(tire.Find(s[i]) > 1)
                flag = false;
        }
        puts(flag ? "YES" : "NO");
    }
    return 0;
}

E - Colored Sticks POJ - 2513 【Medium】

题目大意：

给出一些列颜色，问是否可以将它们前后相连连成一条线。相连的条件是颜色相同。

解题思路：

这就是典型的欧拉回路问题，简单版的可以看 UVa 10129，这里n达到了250000，直接用map是不行了，于是用trie树代替map记录出现的颜色。
剩下的就是求欧拉回路啦，这里还是用的并查集判的底图是否联通。

PS：这题里还要考虑一种特殊情况，就是什么输入也没有，此时也是Possible。

Mycode：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXL = 5000010;
const int MAXN = 500010;

int f[MAXN], deg[MAXN];
int nex[MAXL][26], tot;
void init()
{
    for(int i = 1; i < MAXN; ++i)
        f[i] = i;
}
int Find(int x)
{
    if(x != f[x])
        f[x] = Find(f[x]);
    return f[x];
}
void Union(int u, int v)
{
    int t1 = Find(u);
    int t2 = Find(v);
    if(t1 != t2)
        f[t1] = t2;
}
int add(char *str)
{
    int now = 1;
    for(int i = 0; str[i]; ++i)
    {
        if(!nex[now][str[i]-'a'])
            nex[now][str[i]-'a'] = ++tot;
        now = nex[now][str[i]-'a'];
    }
    return now;
}
int main()
{
    init();
    char s1[11], s2[11];
    while(~scanf("%s%s", s1, s2))
    {
        int t1 = add(s1);
        int t2 = add(s2);
        ++deg[t1], ++deg[t2];
        Union(t1, t2);
    }
    int odd = 0, root = 0;
    for(int i = 1; i <= tot; ++i)
    {
        if(deg[i] & 1)  ++odd;
        if(deg[i] && f[i] == i) ++root;
        if(odd > 2 || root > 1) break;
    }
    if(((odd == 0 || odd == 2) && root == 1) || (root == 0 && odd == 0))
        puts("Possible");
    else
        puts("Impossible");
    return 0;
}

F - Anagram Groups POJ - 2408

题目大意：

解题思路：

Mycode：

1
2


G - 统计难题 HDU - 1251 【Easy】

题目大意：

给出一系列单词，空行分割后查询接下来给出的单词是前面的多少单词的前缀。

解题思路：

建树直接做。

Mycode：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX = 4e5+5;

struct Tire
{
    int nex[MAX][26], pre[MAX], cnt[MAX], tot;
    void init()
    {
        memset(nex, 0, sizeof(nex));
        pre[tot = 1] = 0;   //tot = 1, pre[1] = 0;
    }
    void add(char* str)
    {
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            if(!nex[now][str[i]-'a'])
                nex[now][str[i]-'a'] = ++tot;
            now = nex[now][str[i]-'a'];
            pre[now]++;

            /*for(int j = 0; j <= i; ++j) cout << str[j];
            cout << "   " << pre[now] << endl;*/
        }
        cnt[now]++;
    }
    int Find(char* str)
    {
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            if(!nex[now][str[i]-'a'])
                return 0;
            now = nex[now][str[i]-'a'];
        }
        return pre[now];
    }
}tire;

int main()
{
    char s[11];
    tire.init();
    while(gets(s))
    {
        if(strlen(s) == 0)  break;
        tire.add(s);
    }
    while(gets(s))
    {
        printf("%d\n",tire.Find(s));
    }
    return 0;
}

H - What Are You Talking About HDU - 1075 【Easy】

题目大意：

给出单词代表另一个单词，然后给出一段话输出它代表的话。

解题思路：

记录然后替换就好了，然后就是比较麻烦的模拟了。
这里的trie树完全可以用map代替。

Mycode：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
using namespace std;
const int MAX = 1000005;

struct Tire
{
    int tot, nex[MAX][26], pre[MAX], cnt[MAX];
    char res[MAX][11];
    void init()
    {
        tot = 1;
        memset(nex, 0, sizeof(nex));
//        memset(pre, 0, sizeof(pre));
        memset(cnt, 0, sizeof(cnt));
        memset(res, 0, sizeof(res));
    }
    void add(char *str, char *q)
    {
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            if(!nex[now][str[i]-'a'])
                nex[now][str[i]-'a'] = ++tot;
            now = nex[now][str[i]-'a'];
//            pre[now]++;
        }
        cnt[now]++;
        strcpy(res[now], q);
    }
    int Find(const char *str)
    {
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            if(!nex[now][str[i]-'a'])
                return 0;
            now = nex[now][str[i]-'a'];
        }
//        return pre[now];
        return now;
    }
} tire;
int main()
{
    string trs;
    char op[3333];
    char s[11], t[11];
    tire.init();
    scanf("%s", s);
    while(scanf("%s", s) && s[0] != 'E')
    {
        scanf("%s", t);
        tire.add(t, s);
    }
    getchar();gets(s);
    while(gets(op) && op[0] != 'E')
    {
        int len = strlen(op);
        for(int i = 0; i < len;)
        {
            if(islower(op[i]))
            {
                trs = "";
                int j;
                for(j = 0; isalpha(op[i]); ++j, ++i)
                {
                    trs+=op[i];
                }
                int tt = tire.Find(trs.c_str());
                if(tire.cnt[tt])
                    printf("%s", tire.res[tt]);
                else
                    cout << trs;
            }
            else
            {
                printf("%c", op[i++]);
            }
        }
        puts("");
    }
    return 0;
}

I - Hat’s Words HDU - 1247 【Easy】

题目大意：

给出若干单词，找出可以由其中的两个单词连接后凑成新的单词的单词(就是一个单词可以由已经存在的俩个单词凑成)。
这里不用想复杂了，假设有a和aa两个单词，aa也是满足条件的。

解题思路：

建树后，暴力枚举每个单词是否可以被凑成就行了。

Mycode：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX = 50010;

int idx;
string t1, t2;
char s[MAX][1010];
struct Tire
{
    int nex[MAX][26], pre[MAX], cnt[MAX], tot;
    void init()
    {
        memset(nex, 0, sizeof(nex));
//        memset(pre, 0, sizeof(pre));
        memset(cnt, 0, sizeof(cnt));
        tot = 1;
    }
    void add(char *str)
    {
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            if(!nex[now][str[i]-'a'])
                nex[now][str[i]-'a'] = ++tot;
            now = nex[now][str[i]-'a'];
        }
        cnt[now]++;
    }
    int Find(const char *str)
    {
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            if(!nex[now][str[i]-'a'])
                return 0;
            now = nex[now][str[i]-'a'];
        }
        return cnt[now];
    }
}tire;
bool judge(const string &p)
{
    if(p.size() == 1)    return false;
    int k1, k2;
    for(int i = 1; i < p.size(); ++i)
    {
        t1 = p.substr(0,i);
        t2 = p.substr(i, p.size());
        k1 = tire.Find(t1.c_str());
        k2 = tire.Find(t2.c_str());
        //cout << t1 << " " << k1 << " " << t2 << " " << k2 << endl;
        if(k1 && k2)
            return true;
    }
    return false;
}
int main()
{
    tire.init();
    while(~scanf("%s", s[idx]))
        tire.add(s[idx++]);
    /*for(int i = 1; i <= tire.tot; ++i)
    {
        cout << tire.cnt[i] << endl;
    }*/
    /*for(int i = 0; i < idx; ++i)
    {
        cout << tire.Find(s[i]) << endl;
    }*/
    for(int i = 0; i < idx; ++i)
    {
        if(judge(s[i]))
        {
            printf("%s\n", s[i]);
        }
    }
    return 0;
}

J - Phone List HDU - 1671 【Easy】

题目大意：

判断是否有前缀。

解题思路：

建树直接判。

Mycode：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX = 1e5 + 5;

struct Tire
{
    int tot, nex[MAX][11], pre[MAX], cnt[MAX];
    void init()
    {
        tot = 1;
        memset(nex, 0, sizeof(nex));
        memset(pre, 0, sizeof(pre));
//        memset(cnt, 0, sizeof(cnt));
    }
    void add(char *str)
    {
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            if(!nex[now][str[i]-'0'])
                nex[now][str[i]-'0'] = ++tot;
            now = nex[now][str[i]-'0'];
            pre[now]++;
        }
//        cnt[now]++;
    }
    int Find(char *str)
    {
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            if(!nex[now][str[i]-'0'])
                return 0;
            now = nex[now][str[i]-'0'];
        }
        return pre[now];
    }
}tire;
int main()
{
    int t, n;
    char s[MAX][11];
    scanf("%d",&t);
    while(t--)
    {
        tire.init();
        scanf("%d",&n);
        for(int i = 0; i < n; ++i)
        {
            scanf("%s", s[i]);
            tire.add(s[i]);
        }
        bool flag = true;
        for(int i = 0; i < n && flag; ++i)
        {
            if(tire.Find(s[i]) > 1)
                flag = false;
        }
        puts(flag ? "YES" : "NO");
    }
    return 0;
}

K - Immediate Decodability HDU - 1305 【Easy】

题目大意：

判断给出的字符串判断是否出现了某个串是另外一个的前缀。

解题思路：

建树直接判。

Mycode：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
using namespace std;
const int MAX = 1e5 + 5;

struct Tire
{
    int tot, nex[MAX][11], pre[MAX], cnt[MAX];
    void init()
    {
        tot = 1;
        memset(nex, 0, sizeof(nex));
        memset(pre, 0, sizeof(pre));
        memset(cnt, 0, sizeof(cnt));
    }
    void add(char *str)
    {
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            if(!nex[now][str[i]-'0'])
                nex[now][str[i]-'0'] = ++tot;
            now = nex[now][str[i]-'0'];
            pre[now]++;
        }
        cnt[now]++;
    }
    int Find(char *str)
    {
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            if(!nex[now][str[i]-'0'])
                return 0;
            now = nex[now][str[i]-'0'];
        }
        return pre[now];
    }
}tire;
int main()
{
    int cas = 0, idx = 0;
    char a[11];
    char s[11][11];
    tire.init();
    while(~scanf("%s", a))
    {
        if(a[0] == '9')
        {
            /*for(int i = 0; i < idx; ++i)
                cout << s[i] << endl;*/
            bool flag = true;
            for(int i = 0; i < idx; ++i)
            {
                if(tire.Find(s[i]) > 1)
                {
                    //cout << tire.Find(s[i]) << "  " << s[i] << endl;
                    flag = false;
                    break;
                }
            }
            printf("Set %d is ", ++cas);
            if(flag)
                puts("immediately decodable");
            else
                puts("not immediately decodable");
            tire.init();
            idx = 0;
            memset(s, 0, sizeof(s));
        }
        strcpy(s[idx++], a);
        tire.add(a);
    }
    return 0;
}

L - 单词数 HDU - 2072 【Easy】

题目大意：

给出一篇文章，问文中出现的不同单词的数量。

解题思路：

这个用map就可以，放到这里当做练习了。

PS：这题数据有点恶心，会出现开头空格、连续多个空格、全是空格等很XX的情况，这里我用stringstream处理的——STL大法好！

Mycode：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
using namespace std;
const int MAX = 1e5 + 5;

struct Tire
{
    int tot, nex[MAX][11], pre[MAX], cnt[MAX];
    void init()
    {
        tot = 1;
        memset(nex, 0, sizeof(nex));
        memset(pre, 0, sizeof(pre));
        memset(cnt, 0, sizeof(cnt));
    }
    void add(char *str)
    {
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            if(!nex[now][str[i]-'0'])
                nex[now][str[i]-'0'] = ++tot;
            now = nex[now][str[i]-'0'];
            pre[now]++;
        }
        cnt[now]++;
    }
    int Find(char *str)
    {
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            if(!nex[now][str[i]-'0'])
                return 0;
            now = nex[now][str[i]-'0'];
        }
        return pre[now];
    }
}tire;
int main()
{
    string s;
    char a[1111];
    while(getline(cin, s))
    {
        if(s.size() == 1 && s[0] == '#')    break;
        tire.init();
        stringstream ss(s);
        while(ss >> a)
        {
            tire.add(a);
        }
        int res = 0;
        for(int i = 1; i <= tire.tot; ++i)
            if(tire.cnt[i])  ++res;
        cout << res << "\n";
    }
    return 0;
}

M - T9 HDU - 1298

题目大意：

解题思路：

Mycode：

1
2


N - DNA Prefix LightOJ - 1224 【Medium】

题目大意：

T组数据，每组有N个由ACGT组成的字符串，定义result为 某个前缀的长度 * 拥有这个前缀的字符串的数量，问最大的result是多少。

解题思路：

直接枚举每个前缀，看结果是多少。

  1. 枚举每个字符串的前缀，TLE。

  2. 从树上枚举。这里我想到了两种方法，一是在建树时记录答案并不断更新，二是建完树后从根结点向下搜索，答案就是 此时前缀数 * 此时的深度，计算并更新最大值就行了。

有点要注意的是只会出现ACGT四种字母，我们可以直接将他们标记为0123，这样省下了部分空间。

Mycode：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
const int MAX = 1e6+5;

int t, n, res;
char s[55];
map<char, int> mapa;
struct Tire
{
    int tot, nex[MAX][4], pre[MAX];
    void init()
    {
        memset(nex, 0, sizeof(nex));
        memset(pre, 0, sizeof(pre));
        tot = 1;
    }
    void add(char *str)
    {
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            if(!nex[now][mapa[str[i]]])
                nex[now][mapa[str[i]]] = ++tot;
            now = nex[now][mapa[str[i]]];
            pre[now]++;
        }
    }
    void dfs(int now, int dep)
    {
        for(int i = 0; i < 4; ++i)
        {
            if(nex[now][i])
                dfs(nex[now][i], dep+1);
        }
        if(pre[now] * dep > res)
            res = pre[now] * dep;
    }
    /*int Find(const char *str)
    {
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            if(!nex[now][mapa[str[i]]])
                return 0;
            now = nex[now][mapa[str[i]]];
        }
        return pre[now];
    }*/
}tire;
void init()
{
    mapa['A'] = 0;
    mapa['C'] = 1;
    mapa['G'] = 2;
    mapa['T'] = 3;
}
int main()
{
    init();
    scanf("%d", &t);
    for(int cas = 1; cas <= t; ++cas)
    {
        res = 0;
        tire.init();
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            scanf("%s", &s), tire.add(s);
        //从根结点向下搜索，当前深度为0
        tire.dfs(1,0);
        printf("Case %d: %d\n", cas, res);
    }
    return 0;
}

O - Consistency Checker LightOJ - 1129 【Easy】

题目大意：

给出T个清单，每个清单上有n个互不相同的电话号码，每个电话号码长度在1 ~ 10之间，问这些清单是否具有一致性，即这张清单中的每个电话号码都不是其他某个号码的前缀。

解题思路：

建树，判断即可。

Mycode：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX = 1e5+5;

int t, n;
bool flag;
char s[10010][11];
struct Tire
{
    int nex[MAX][11], pre[MAX], cnt[MAX], tot;
    void init()
    {
        tot = 1;
        memset(nex, 0, sizeof(nex));
        memset(pre, 0, sizeof(pre));
//        memset(cnt, 0, sizeof(cnt));
    }
    void add(char* str)
    {
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            if(!nex[now][str[i]-'0'])
                nex[now][str[i]-'0'] = ++tot;
            now = nex[now][str[i]-'0'];
            pre[now]++;

            /*for(int j = 0; j <= i; ++j) cout << str[j];
            cout << "   " << pre[now] << endl;*/
        }
//        cnt[now]++;
    }
    int Find(char* str)
    {
        int now = 1;
        for(int i = 0; str[i]; ++i)
        {
            if(!nex[now][str[i]-'0'])
                return 0;
            now = nex[now][str[i]-'0'];
        }
        return pre[now];
    }
} tire;

int main()
{
    scanf("%d", &t);
    for(int cas = 1; cas <= t; ++cas)
    {
        scanf("%d",&n);
        tire.init();
        flag = true;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%s", s[i]);
            tire.add(s[i]);
        }
        for(int i = 1; i <= n; ++i)
        {
            if(tire.Find(s[i]) > 1)
            {
                flag = false;
                break;
            }
        }
        printf("Case %d: %s\n", cas, flag ? "YES" : "NO");
    }
    return 0;
}

P - Consecutive Sum LightOJ - 1269

题目大意：

解题思路：

Mycode：

1
2


Donate comment here
0%