字典树
像查字典一样，将字符存到树的节点上。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
using namespace std;
struct node {
array<int, 26> son;
bool isend;
int prenum;
bool repeat;
};
struct Trie {
vector<node> tr;
int N;
int siz;
Trie(int N) : N(N), siz(0) {
tr.assign(N, {});
}
void insert(string s) {
int p = 0;
for (int i = 0; i < s.size(); i++) {
int ch = s[i] - 'a';
if (tr[p].son[ch] == 0) {
tr[p].son[ch] = ++siz;
}
p = tr[p].son[ch];
tr[p].prenum++;
if (i == s.size() - 1) {
tr[p].isend = 1;
}
}
}
int query(string s) {
int now = 0;
for (int i = 0; i < s.size(); i++) {
int ch = s[i] - 'a';
if (!tr[now].son[ch]) {
return 3;
}
now = tr[now].son[ch];
}
if (!tr[now].isend) return 3;
if (!tr[now].prenum) return 3;
if (tr[now].repeat == 0) {
tr[now].repeat = true;
return 1;
}
return 2;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
Trie bk(800000);
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
bk.insert(s);
}
int m;
cin >> m;
for (int i = 0; i < m; i++) {
string s;
cin >> s;
int f = bk.query(s);
switch (f) {
case 1:
cout << "OK" << '\n';
break;
case 2:
cout << "REPEAT" << '\n';
break;
case 3:
cout << "WRONG" << '\n';
}
}
return 0;
}
- 最大异或路径
将一个数字的二进制看成一个字符串，可以建成一个01-trie树，可以维护很多的信息，例题： 求最长异或路径
P4551 最长异或路径 - 洛谷
- 思路，任意选定一个点作为根，那么从 i 到 j 的异或就等于 从根到 i 异或 从根到j （重叠部分会抑或两次而抵消） ，之后对每个数字，先dfs出所有路径，找到他们到根节点的异或值 与根节点到v的异或值最大的值， 更新答案。
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
using namespace std;
using i64 = long long;
struct Trie {
int n, cnt;
vector<array<int, 2>> tr;
Trie() {}
Trie(int n) : n(n), cnt(1) {
tr.assign(n + 1, {});
}
void insert(int x) {
int p = 0;
for (int i = 30; i >= 0; i--) {
int g = ((x >> i) & 1);
if (tr[p][g] == 0) {
tr[p][g] = ++cnt;
}
p = tr[p][g];
}
}
int get(int x) {
int res = 0;
int p = 0;
for (int i = 30; i >= 0; i--) {
int g = ((x >> i) & 1);
if (tr[p][g ^ 1] != 0) {
p = tr[p][g ^ 1];
res |= (1 << i);
} else {
p = tr[p][g];
}
}
return res;
}
void query() {
}
};
struct node {
int v;
int w;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector e(n + 1, vector<node> {});
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
e[u].push_back({v, w});
e[v].push_back({u, w});
}
Trie trie(10010 << 5);
int ans = 0;
vector<int> dis(n + 1);
auto dfs = [&](auto self, int u, int fa) -> void {
trie.insert(dis[u]);
ans = max(ans, trie.get(dis[u]));
for (auto ed : e[u]) if (ed.v != fa) {
auto [v, w] = ed;
dis[v] = dis[u] ^ w;
self(self, v, u);
}
};
dis[1] = 0;
dfs(dfs, 1, 0);
cout << ans << '\n';
return 0;
}
考虑先将所有数字存到一个字典树中，按照每一位进行分析，
- 如果所有数字的 i 位上都是0， 那么这一位一定填上 0
- 如果所有数字 i位上都是 1， 那么这一位一定填上1（结果这一位一定是0）
- 如果某一位上有 0 又有 1， 如 11000， 11100， 第三位不论别的怎么填，异或后答案这一位上总会是1，dfs即可球的答案
1 |
|