NEFU大一暑假集训-字典树

题集链接

OP

感谢学长的讲解与付出；
感谢ph和zsl两位大佬的指导与讨论；

目前来看，字典树主要用于线性复杂判断给定字符串与字典有没有前缀关系，和给定目标下异或值的求取；

A L语言

题目大意

给定字典，问题给字符串是否为字典中的若干单词拼接起来的；

思路

参考

个人选择了一个比较暴力的做法（只看懂了这个）；
即对每一个作为单词结尾的点的后面都进行单词判断，以此更新最大长度；
详见上链吧；

代码

代码来自上链

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
#include <bits/stdc++.h>
using namespace std;
map<string, bool> m1;
map<string, int> m2;
char s[2000005];
int cnt = 0;
int trie[1005][28];
bool f[2000010];
bool flag[10005];
inline int read()
{
    int ans = 0, fl = 1;
    char i = getchar();
    while (i < '0' || i > '9')
    {
        if (i == '-')
        {
            fl = -1;
        }
        i = getchar();
    }
    while (i >= '0' && i <= '9')
    {
        ans = ans * 10 + i - '0';
        i = getchar();
    }
    return ans * fl;
}
inline void insert()
{
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    int pos = 0;
    for (int i = 1; i <= len; i++)
    {
        int c = s[i] - 'a';
        if (!trie[pos][c])
        {
            trie[pos][c] = ++cnt;
        }
        pos = trie[pos][c];
    }
    flag[pos] = 1;
}
inline int query() //查询
{
    scanf("%s", s + 1);
    if (m1[s + 1])
    {
        return m2[s + 1];
    }
    else
    {
        int len = strlen(s + 1);
        int pos = 0;
        int ans;
        memset(f, false, sizeof(f));
        f[0] = true;
        for (int i = 0; i <= len; i++)
        {
            if (!f[i])
                continue;
            else
                ans = i;
            for (int j = i + 1, p = 0; j <= len; j++)
            {
                int c = s[j] - 'a';
                p = trie[p][c];
                if (!p)
                    break;
                if (flag[p])
                    f[j] = true;
            }
        }
        m1[s + 1] = true;
        m2[s + 1] = ans;
        return ans;
    }
}
int main()
{
    int n, m;
    n = read();
    m = read();
    while (n--)
        insert();
    while (m--)
        cout << query() << endl;
    return 0;
}

B Secret Message 秘密信息

题目大意

用以测试的串是多少个给定串的前缀；

思路

字典树板，用给定串构造好字典树，用测试串去匹配即可；

注意一些特殊情况，如测试串是给定串的前缀等，做好标记；

代码

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
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef int itn;
typedef unsigned long long ull;

inline ll read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return (ll)x*f;
}
int b[100005],g;
int ttre[500005][2],meet[500005],ed[500005],c;
int main()
{
    int n,m;
    cin>>n>>m;
    c=1;
    while(n--)
    {
        
        int k;
        scanf("%d",&k);
        int p=0;
        for(int i=1;i<=k;i++)
        {
            scanf("%d",&g);
            if(!ttre[p][g])ttre[p][g]=c++;//printf("*");
            p=ttre[p][g];
            meet[p]++;
        }
        meet[p]--;
        ed[p]++;
    }
    while(m--)
    {
        int ans=0;
        c=1;
        int k;
        scanf("%d",&k);
        int p=0;
        for(int i=1;i<=k;i++)
        {
            scanf("%d",&b[i]);
        }
        for(int i=1;i<=k;i++)
        {
            p=ttre[p][b[i]];
            if(!p)
            {
                //ans+=meet[p];
                break;
            }
            else
            {
                ans+=ed[p];
                
            }
        }
        ans+=meet[p];
        printf("%d\n",ans);
    }
    return 0;
}

C The XOR-longest Path

题目大意

给定树的结构和每条边的边权，求任意两点间路径上的最小边权异或值；

思路

树的性质有，任意两点间均有且只有一条路径；

异或的性质有，C=AxorB,CxorB=AC=AxorB,CxorB=A；

所以，我们可以通过dfs处理出所有点与一号节点（根）之间路径的边权异或，这样无论所求两点是否为同一枝杈上，都可以 O(1)O(1) 复杂度内求出两点间的路径边权异或值；

接下来把这些处理出的异或值存入字典树，依次在字典树中匹配与其异或值最大的值，并更新答案；此部分复杂度 O(nlogn)O(nlogn) ；

代码

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
#include <stdio.h>
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef int itn;
typedef unsigned long long ull;

inline ll read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return (ll)x * f;
}
//stack<int> stk;
int ttre[3200006][2], ed[3200006], val[100005], rch[100005]; //val[300005];
vector<pair<int, int> > rod[100005];

void dfs(int x)
{
    for (int i = 0; i < rod[x].size(); i++)
    {
        if (!rch[rod[x][i].first])
        {
            rch[rod[x][i].first] = 1;
            val[rod[x][i].first] = (val[x] ^ rod[x][i].second);
            dfs(rod[x][i].first);
        }
    }
}
int main()
{
    int n, g, a, b, c;
    while (cin >> n)
    {
        
        for (int j = 1; j <= n - 1; j++)
        {
            scanf("%d%d%d", &a, &b, &c);
            rod[a].push_back(make_pair(b, c));
            rod[b].push_back(make_pair(a, c));
        } //printf("*");
        rch[1] = 1;
        dfs(1);
        c = 1;
        //printf("*");
        for (int j = 1; j <= n; j++)
        {
            int p = 0;
            for (int i = 30; i >= 0; i--)
            {
                g = (val[j] >> i) & 1;
                if (!ttre[p][g])
                    ttre[p][g] = c++;
                p = ttre[p][g];
            }
            //ed[p]++;
        }
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            int tmp = 0, p = 0;
            for (int j = 30; j >= 0; j--)
            {
                if (ttre[p][!((val[i] >> j) & 1)])
                {
                    tmp += 1 << j;
                    p = ttre[p][!((val[i] >> j) & 1)];
                }
                else
                    p = ttre[p][((val[i] >> j) & 1)];
            }
            ans = max(ans, tmp);
        }
        cout << ans << endl;
        for (int i = 1; i <= n; i++)
        {
            val[i] = 0;
            rch[i] = 0;
            rod[i].clear();
        }
        for (int i = 0; i < c; i++)
        {
            ttre[i][0] = 0;
            ttre[i][1] = 0;
        }
    }
    return 0;
}

D The XOR Largest Pair

题目大意

给定一些数，求任意两数间的异或最大值；

思路

字典树板，将这些数存入字典树，依次在字典树中匹配与其异或值最大的值，并更新答案；

代码

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
#include <stdio.h>
#include <iostream>
#include <stack>
#include <algorithm>
#include <string.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef int itn;
typedef unsigned long long ull;

inline ll read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return (ll)x * f;
}
stack<int>stk;
int ttre[3100006][2],ed[3100006],k[100005];//val[300005];
int c;
int ans=0;

int main()
{
    int n,g;
    cin >> n;
    c=1;
    for(int j=1;j<=n;j++)
    {
        scanf("%d", &k[j]);
        int p = 0;
        for (int i = 30; i>=0; i--)
        {
            g = (k[j]>>i)&1;
            //printf("%d*",g);
            if (!ttre[p][g])
                ttre[p][g] = c++;
            p = ttre[p][g];
            //val[p]=g;
        }
        ed[p]++;
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int tmp=0,p=0;
        for(int j=30;j>=0;j--)
        {
            if(ttre[p][!((k[i]>>j)&1)])
            {
                tmp+=1<<j;
                p=ttre[p][!((k[i]>>j)&1)];
            }
            else  p=ttre[p][((k[i]>>j)&1)];
        }
        ans=max(ans,tmp);
    }
    cout<<ans;
    return 0;
}

E Phone List

题目大意

给定 n 个长度不超过 10 且各异的数字串，问其中是否存在两个数字串 S,T，使得 S 是 T 的前缀。

思路

字典树板，接收到的都存入字典树后，检测字典树中是否有前缀关系即可；

注意不能用 lld 接收，存在前导零；

代码

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
#include <stdio.h>
#include <iostream>
#include <stack>
#include <algorithm>
#include <string.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef int itn;
typedef unsigned long long ull;

inline ll read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return (ll)x * f;
}
int g;
int ttre[100005][10], meet[100005], ed[100005], c;
char k[12];
int main()
{
    int n;
    itn t;
    cin >> t;
    while (t--)
    {
        int f = 0;
        cin >> n;
        c = 1;
        while (n--)
        {
            scanf("%s",&k);
            int p = 0;
            for (int i = 0; k[i]; i++)
            {
                g = k[i] - '0';
                //printf("%d*",g);
                if (!ttre[p][g])
                    ttre[p][g] = c++;
                p = ttre[p][g];
                meet[p]++;
            }
            //meet[p]--;
            ed[p]++;
        }
        for (int i = 0; i < c; i++)
        {
            if (ed[i] && meet[i] >= 2)
                f = 1;
            ed[i]=0;
            meet[i]=0;
            memset(ttre[i],0,sizeof ttre[i]);
        }
        if (f)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}

F Xor sum

题目大意

给定n个数和一个数k，求出最短的连续的一段数，使得它们的异或和大于等于k，如果没有则输出-1。

思路

参考

对于给定的每一个数，在存入字典树之前先判断并更新答案，这样搜索范围内的只有它前面的数，此时即为固定右端点找左端点；

每个数在树中存储的结尾要记录这个数最后一次出现的下标，这样就可以使区间尽可能小；

注意无论这位的异或值是1还是0，只要合法，就应计算，之后取最大值；

代码

代码来自上链

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <stdio.h>
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef int itn;
typedef unsigned long long ull;

inline ll read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return (ll)x * f;
}
const int N = 1e5 + 10;
int trie[N * 31][2], mx[N * 31], fa[N * 31], tot = 0;

void init()
{
    trie[0][0] = trie[0][1] = 0;
    for (int i = 0; i <= tot; i++)
    {
        mx[i] = fa[i] = 0;
    }
    tot = 0;
}

void insert(int x, int pos)
{
    int temp[31];
    for (int i = 30; i >= 1; i--)
    {
        temp[i] = x & 1;
        x >>= 1;
    }
    int now = 0;
    for (int i = 1; i <= 30; i++)
    {
        int p = now;
        mx[now] = pos;
        if (trie[now][temp[i]])
            now = trie[now][temp[i]];
        else
        {
            trie[now][temp[i]] = ++tot;
            trie[tot][0] = trie[tot][1] = 0;
            now = tot;
        }
        fa[now] = p;
    }
    mx[now] = pos;
}

int query(int r, int k, int now, int sum, int bit)
{
    if (sum >= k)
        return mx[now];
    if (sum + (1 << (bit + 1)) <= k)
        return 0;
    int ans = 0;
    if (trie[now][0])
    {
        int temp = (r & (1 << bit));
        ans = max(ans, query(r, k, trie[now][0], sum + temp, bit - 1));
    }
    if (trie[now][1])
    {
        int temp = (r & (1 << bit) ^ (1 << bit));
        ans = max(ans, query(r, k, trie[now][1], sum + temp, bit - 1));
    }
    return ans;
}

int main()
{
    int T = 1;
    T = read();
    while (T--)
    {
        init();
        int n, k;
        n = read();
        k = read();
        int ans = n + 1, l = -1, r = -1;
        int sum = 0;
        for (int i = 1; i <= n; i++)
        {
            int a = read();
            sum ^= a;
            if (sum >= k)
            {
                if (ans > i)
                {
                    ans = i;
                    l = 1;
                    r = i;
                }
            }

            int d = query(sum, k, 0, 0, 29);
            if (d > 0 && ans > i - d)
            {
                ans = i - d;
                l = d + 1;
                r = i;
            }

            insert(sum, i);
        }
        if (ans == n + 1)
            printf("-1\n");
        else
            printf("%d %d\n", l, r);
    }
}

ED

\

算法竞赛 > 比赛与题集
NEFU大一暑假集训-字典树
https://tanyuu.github.io/2021.07-12/NEFU大一暑假集训-字典树/
作者
F Juny
发布于
2021年7月29日
许可协议