voidinsert(string s){ int len = s.size(); int now = 1; for (int i = 0; i < len; ++i) { int k = s[i] - 'a';// 当前字母 if (node[now][k] == 0) node[now][k] = ++tot;//如果此时没有节点,就新建节点 now = node[now][k]; } exist[now] = true;//标记,表示此时的now对应有结果 return ; }
boolsearch(string s){ int len = s.size(); int now = 1; for (int i = 0; i < len; ++i) { int k = s[i] - 'a'; if (node[now][k] == 0) returnfalse;//如果此时没有结果,则直接返回false now = node[now][k]; } return exist[now];//这里的exist意义和上面的一样,表示此时的now有没有结果 }
intmain(){ cin >> n; for (int i = 1; i <= n; ++i) { cin >> s; insert(s); } cin >> m; for (int i = 1; i <= m; ++i) { cin >> s; puts(search(s) == true ? "Yes" : "No"); } return0; }
代码注意点:
Trie数组空间要开到 字符串个数×不同的字符个数。
代码中的 tot 和 now 的初始值必须相同,例如:我们定义 tot 初始为0,那么 now 初始也得为0。
voidinsert(string s){ int len = s.size(); int now = 1; for (int i = 0; i < len; ++i) { int k = s[i] - 'a'; if (node[now][k] == 0) node[now][k] = ++tot; now = node[now][k]; } exist[now]++; return ; }
string search(string s){ int len = s.size(); int now = 1; for (int i = 0; i < len; ++i) { int k = s[i] - 'a'; if (node[now][k] == 0) return"WRONG"; now = node[now][k]; } if (exist[now] == 0) return"WRONG"; elseif (exist[now] == 1) return"OK"; elsereturn"REPEAT"; }
intmain(){ cin >> n; for (int i = 1; i <= n; ++i) { cin >> s; insert(s); } cin >> m; for (int i = 1; i <= m; ++i) { cin >> s; string res = search(s); cout << res << endl; if (res == "OK") insert(s); } return0; }
int n, m, L, tot; string s; int res[N], node[1005][N][26]; bool exist[1005][N * 26];
voidinsert(int Case, string s){ int len = s.size(); int now = 0; for (int i = 0; i < len; ++i) { int k = s[i] - 'a'; if (node[Case][now][k] == 0) node[Case][now][k] = ++tot; now = node[Case][now][k]; } exist[Case][now] = true; }
boolsearch(int Case, string s){ int len = s.size(); int now = 0; for (int i = 0; i < len; ++i) { int k = s[i] - 'a'; if (node[Case][now][k] == 0) returnfalse; now = node[Case][now][k]; } return exist[Case][now]; }
intmain(){ cin >> n; for (int i = 1; i <= n; ++i) { cin >> L; for (int j = 1; j <= L; ++j) { cin >> s; insert(i, s); } } cin >> m; for (int i = 1; i <= m; ++i) { cin >> s; int cnt = 0; for (int j = 1; j <= n; ++j) { if (search(j, s) == true) res[++cnt] = j; } for (int j = 1; j <= cnt; ++j) { if (j != 1) printf(" "); printf("%d", res[j]); } cout << endl; } return0; }
01 Trie
引入
我们如果要给定两个数组 a 和 b,均有 n 个数,我们固定 a 不动,让 b 自由排列,使排列后的 b[i] xor a[i] 的值最大,求字典序最小的答案。
方法一
暴力枚举 b 的排列,取最大值即可,时间复杂度 O(n!×n),随便就卡死了。
方法二 - 01 Trie
本质上是一种贪心。我们发现:
二进制高位尽量不同,异或出的值就会越大。
有了这个性质,就发现我们处理二进制位就行了。发现,此时只要求二进制高位开始的第 i 位有相同的或者是没相同的即可。于是,便发现可以用Trie来维护。
时间复杂度: O(nlogmax(ai,bi)),在 int 范围内,即可理解为 O(nlogn),时间复杂度极其优秀,空间也就 O(2×nlogn)。
voidinsert(int x){ int now = 1; Tree[now].count++; for (int i = 30; i >= 0; --i) { int key = x >> i & 1;//取x从右往左数第i位 if (Tree[now].son[key] == 0) Tree[now].son[key] = ++tot; now = Tree[now].son[key]; Tree[now].count++; } return ; }
intsearch(int x){ int result = 0, now = 1; for (int i = 30; i >= 0; --i) { int key = x >> i & 1; if (Tree[Tree[now].son[key]].count == 0) key ^= 1; result = (result << 1) + key; now = Tree[now].son[key]; Tree[now].count--; } return x ^ result; }
intmain(){ std::cin >> n; for (int i = 1; i <= n; ++i) { std::cin >> a[i]; } for (int i = 1; i <= n; ++i) { std::cin >> b[i]; insert(b[i]); } for (int i = 1; i <= n; ++i) { std::cout << search(a[i]) << " "; } return0; }
int n, ans, tot = 1; int u, v, w; int dis[N], vis[N];
int Tree[N * 31][2];
voidaddEdge(int u, int v, int w){ G[u].push_back((edge){v, w}); }
voidPrework(int k){//取出dis(k)的值 for (vector <edge> :: iterator it = G[k].begin(); it != G[k].end(); ++it) { int to = it -> to, v = it -> w; if (vis[to] == 1) continue ; dis[to] = dis[k] ^ v; vis[to] = 1; Prework(to); } return ; }
voidinsert(int k){//01Trie板子 int now = 1, key; for (int i = 31; ~i; --i) { key = k >> i & 1; if (Tree[now][key] == 0) Tree[now][key] = ++tot; now = Tree[now][key]; } return ; }
intsearch(int k){//01Trie板子 int now = 1, res = 0, key; for (int i = 31; ~i; --i) { key = k >> i & 1; key ^= 1; if (Tree[now][key] == 0) key ^= 1; res = (res << 1) + key; now = Tree[now][key]; } return res; }
intmain(){ cin >> n; for (int i = 1; i <= n - 1; ++i) { cin >> u >> v >> w; addEdge(u, v, w), addEdge(v, u, w); } vis[1] = 1; Prework(1); for (int i = 1; i <= n; ++i) { insert(dis[i]); if (i != 1) ans = max(ans, dis[i] ^ search(dis[i])); } cout << ans << endl; return0; }
voidInsert(int k){ int now = 1, key; for (int i = MAXBIT; ~i; --i) { key = k >> i & 1; if (Tree[now][key] == 0) Tree[now][key] = ++tot; now = Tree[now][key]; Size[now]++; } Exist[now]++; return ; }
2 删除
跟插入实现差不多,代码:
1 2 3 4 5 6 7 8 9 10
voidDelete(int k){ int now = 1, key; for (int i = MAXBIT; ~i; --i) { key = k >> i & 1; now = Tree[now][key]; Size[now]--; } Exist[now]--; return ; }
查询 k 的排名
对于 k 的第 i 位,如果为 1 ,计数器就加 Size[lson(now)],否则就不加,最后输出计数器+1即可。代码:
1 2 3 4 5 6 7 8 9
intRank(int k){ int now = 1, res = 0, key; for (int i = MAXBIT; ~i; --i) { key = k >> i & 1; if (key == 1) res += Size[Tree[now][0]]; now = Tree[now][key]; } return res + 1; }
查询排名为 k 的数
首先实现 Count(k) 函数,表示数 k 的出现次数。
实现 GetKth(k) 时。
如果 k 的第 i 位为 0
继续向下转移即可
如果 k 的第 i 位为 1
先用 k 减去 Size[lson(now)],计数器|=2i,再转移即可。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13
intGetKth(int k){ int now = 1, key, res = 0; for (int i = MAXBIT; ~i; --i) { key = k >> i & 1; if (k <= Size[Tree[now][0]]) now = Tree[now][0]; else { k -= Size[Tree[now][0]]; res |= (1 << i); now = Tree[now][1]; } } return res; }
namespace Trie { constint N = 1e5 + 5; constint MAXBIT = 23; int tot = 1, Tree[N * MAXBIT][2], Exist[N * MAXBIT * 2], Size[N * MAXBIT * 2];
voidInsert(int k){ int now = 1, key; for (int i = MAXBIT; ~i; --i) { key = k >> i & 1; if (Tree[now][key] == 0) Tree[now][key] = ++tot; now = Tree[now][key]; Size[now]++; } Exist[now]++; return ; } voidDelete(int k){ int now = 1, key; for (int i = MAXBIT; ~i; --i) { key = k >> i & 1; now = Tree[now][key]; Size[now]--; } Exist[now]--; return ; } intCount(int k){ int now = 1, key; for (int i = MAXBIT; ~i; --i) { key = k >> i & 1; now = Tree[now][key]; if (now == 0) return0; } return Exist[now]; } intRank(int k){ int now = 1, res = 0, key; for (int i = MAXBIT; ~i; --i) { key = k >> i & 1; if (key == 1) res += Size[Tree[now][0]]; now = Tree[now][key]; } return res + 1; } intGetKth(int k){ int now = 1, key, res = 0; for (int i = MAXBIT; ~i; --i) { key = k >> i & 1; if (k <= Size[Tree[now][0]]) now = Tree[now][0]; else { k -= Size[Tree[now][0]]; res |= (1 << i); now = Tree[now][1]; } } return res; } intGetPre(int k){ int res; Insert(k); res = GetKth(Rank(k) - 1); Delete(k); return res; } intGetNext(int k){ int res; Insert(k); res = GetKth(Rank(k) + Count(k)); Delete(k); return res; } }