浅谈Trie树算法

于是他错误的点名开始了

题目背景

XS中学化学竞赛组教练是一个酷爱炉石的人。

他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次，然后正好被路过的校长发现了然后就是一顿欧拉欧拉欧拉（详情请见已结束比赛 CON900）。

题目描述

这之后校长任命你为特派探员，每天记录他的点名。校长会提供化学竞赛学生的人数和名单，而你需要告诉校长他有没有点错名。（为什么不直接不让他玩炉石。）

输入格式

第一行一个整数 $n$，表示班上人数。

接下来 $n$ 行，每行一个字符串表示其名字（互不相同，且只含小写字母，长度不超过 $50$）。

第 $n+2$ 行一个整数 $m$，表示教练报的名字个数。

接下来 $m$ 行，每行一个字符串表示教练报的名字（只含小写字母，且长度不超过 $50$）。

输出格式

对于每个教练报的名字，输出一行。

如果该名字正确且是第一次出现，输出 OK，如果该名字错误，输出 WRONG，如果该名字正确但不是第一次出现，输出 REPEAT。

样例 #1

样例输入 #1

5  
a
b
c
ad
acd
3
a
a
e

样例输出 #1

OK
REPEAT
WRONG

提示

• 对于 $40\%$ 的数据，$n\le 1000$，$m\le 2000$。
• 对于 $70\%$ 的数据，$n\le 10^4$，$m\le 2\times 10^4$。
• 对于 $100\%$ 的数据，$n\le 10^4$，$m\le 10^5$。

$\text{upd 2022.7.30}$：新增加一组 Hack 数据。

思路

大概的思想就是对所有名字建 trie，再在 trie 中查询字符串是否存在、是否已经点过名，第一次点名时标记为点过名。
可以从这道题中理解 trie 相对于暴力枚举的优越性：将很多信息放在了一起计算，并且将一些无用的信息直接抛弃掉了。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=500010;
char s[60];
int n,m,ch[N][26],tag[N],tot=1;
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",s+1);int u=1;for(int j=1;s[j];j++){int c=s[j]-'a';if(!ch[u][c])ch[u][c]=++tot;u=ch[u][c];}tag[u]=1;}scanf("%d",&m);while(m--){scanf("%s",s+1);int u=1;for(int j=1;s[j];j++){int c=s[j]-'a';u=ch[u][c];if(!u)break;}if(tag[u]==1){tag[u]=2;puts("OK");}else if(tag[u]==2)puts("REPEAT");else puts("WRONG");}
}

01Trie

顾名思义，即字符集只有 0/1 的 Trie 树。
常被用来解决有关异或值的问题。
为什么？
异或有着按位考虑的性质，每一位的贡献是分开的，这与 Trie 树用不同的深度存不同的位的性质是吻合的。
如果要最大化异或值，一定是先最大化其最高位，这有一点贪心的思想。所以如果用
Trie 树从高到低来做，正好吻合了这个贪心的思想。

求n个数两两异或的最大值

$1\le N\le 10^5,0\le A_i<2^{31}$将这n个数转成二进制，然后插入到 Trie 树里。
接着再取每个数，在 trie 树上跑一遍，在可能的情况下尽量走与该二进制位不同的方向。
这里用到了贪心的思想，因为二进制下 1xxxxx > 0yyyyy 总是成立的，高位优一定全局优。

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
int ch[2];
}a[3000000];
bool num[40];
bool ans[40];
int tot=0;
int f[40];
void insert(int x)
{
memset(num,0,sizeof(num));
for(int i=0;x;i++)
{
num[i]=x&1;
x>>=1;
}
int root=0;
for(int i=30;i>=0;i--)
{
if(!a[root].ch[num[i]])a[root].ch[num[i]]=++tot;
root=a[root].ch[num[i]];
}
}
int find(int x)
{
memset(num,0,sizeof(num));
memset(ans,0,sizeof(ans));
int fh=0;
for(int i=0;x;i++)
{
num[i]=x&1;
x>>=1;
}
int root=0;
for(int i=30;i>=0;i--)
{
if(a[root].ch[num[i]^1])root=a[root].ch[num[i]^1],ans[i]=1;
else root=a[root].ch[num[i]],ans[i]=0;
}
for(int i=0;i<=30;i++)fh+=ans[i]*f[i];
return fh;
}
int main()
{
int n,ans=0,t;
f[0]=1;
for(int i=1;i<=30;i++)f[i]=f[i-1]*2;
scanf("%d%d",&n,&t);
insert(t);
for(int i=2;i<=n;i++)
{
scanf("%d",&t);
ans=max(ans,find(t));
insert(t);
}
cout<<ans;
return 0;
}

Nikitosh 和异或

给定一个含 个元素的数组 ，下标从 开始。请找出下面式子的最大值：
$(A[l_1]⨁A[l_1+1]\dots \dots A[r_1])+(A[l_2]⨁A[l_2+1]\dots \dots A[r_2])$
$1\le l_1\le r_1<l_2\le r_2\le N$
x⨁y， 表示 和 的按位异或。
$2\le N\le 4\times 10^5$
$0\le A_i\le 10^9$

思路

首先考虑问题的第一部分，对于一个确定的r任取l，$\underset{i=l}{\overset{r}{⨁}}{a}_i$的最大值是多少？将这个数组计为vl 。
首先区间异或和也可以表示为两个前缀异或和相异或。
这样的话我们只需要对于确定的r，找到 $s_0,s_1,s_2\dots s_{r-1}$里与$s_r$异或值最大的。
这个问题可以从左到右扫一遍，每次在 trie 里查询$s_r$，接着插入$s_r$就好了。
同样的，我们可以求出对于一个确定的l任取r，最大的异或值是多少。将这个数组计
为vr 。
对vl取前缀max，vr取后缀max ，接着枚举i并统计答案$v{l}_i+v{r}_{i+1}$就好了。

AC代码

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N = 4e5 + 10;
int tree[N * 31][2], cnt;
int l[N], r[N], a[N], n;
inline void add(int x, int rt) {for (int i = 31; i >= 0; i--) {int y = ((x >> i) & 1);if (tree[rt][y] == 0)tree[rt][y] = ++cnt;rt = tree[rt][y];}return ;
}
inline int query(int x, int rt) {int res = 0;for (int i = 31; i >= 0; i--) {int y = ((x >> i) & 1);if (tree[rt][y ^ 1]) {res += (1 << i);rt = tree[rt][y ^ 1];} elsert = tree[rt][y];}return res;
}
int main() {scanf("%d", &n);memset(tree, 0, sizeof(tree));cnt = 0;for (int i = 1; i <= n; i++)scanf("%d", &a[i]);l[0] = 0;int x = 0;for (int i = 1; i <= n; i++) {x ^= a[i];add(x, 0);l[i] = max(l[i - 1], query(a[i], 0));}memset(tree, 0, sizeof(tree));r[n + 1] = 0;x = 0;for (int i = n; i >= 1; i--) {x ^= a[i];add(x, 0);r[i] = max(r[i + 1], query(a[i], 0));}int ans = 0;for (int i = 1; i <= n; i++)ans = max(ans, l[i] + r[i + 1]);printf("%d\n", ans);return 0;
}

The XOR-longest Path

给定一棵 n 个点的带权树，求树上最长的异或和路径。
$1\le n\le 10^5$
,$1\le u,v\le n,0\le w<2^{31}$

思路

异或的一个很重要的性质：
x ⊕ x = 0。
所以说，如果一个元素，我们对其进行了重复的异或，但是这个重复次数是偶数次，那
么可以视作没有进行异或。
那么，对于树上的一条路径，我们就有了一个极为优美的表示方式：
$path(x,y)=path(x,lca)\oplus path(lca,y)=path(x,root)\oplus path(y,root)$
只要求出每个点到根节点的异或和（通过 dfs 就可以简单实现），问题就转化为第一道
题，求点对的最大异或值。

AC代码

#include <bits/stdc++.h>
using namespace std;
inline int read() {char ch = getchar();int x = 0;while (!isdigit(ch))ch = getchar();while (isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}return x;
}
const int N = 1e5 + 3;
struct emm {int e, f, v;
} a[2 * N];
int h[N];
int idx = 0;
inline  void con(int x, int y, int l) {a[++idx].f = h[x];h[x] = idx;a[idx].e = y;a[idx].v = l;a[++idx].f = h[y];h[y] = idx;a[idx].e = x;a[idx].v = l;return;
}
int d[N], w[N];
void dfs(int x) {for (int i = h[x]; i; i = a[i].f)if (!d[a[i].e]) {w[a[i].e] = (w[x] ^ a[i].v);d[a[i].e] = d[x] + 1;dfs(a[i].e);}return;
}
struct ahh {int nxt[2];
} tr[3200003];
int cnt = 0;
int b[33];
inline int get(int x) {int j = -1;while (x) {b[++j] = x & 1;x >>= 1;}return j;
}
inline  void add(int x) {memset(b, 0, sizeof(b));int j = get(x);int k = 0;for (int j = 31; j >= 0; --j) {if (!tr[k].nxt[b[j]])tr[k].nxt[b[j]] = ++cnt;k = tr[k].nxt[b[j]];}return;
}
inline long long find(int x) {memset(b, 0, sizeof(b));int j = get(x);long long now = 0;int k = 0;for (int j = 31; j >= 0; --j) {if (tr[k].nxt[1 - b[j]]) {now += (1 << j);k = tr[k].nxt[1 - b[j]];} elsek = tr[k].nxt[b[j]];}return now;
}
int main() {int n = read();for (int i = 1; i < n; ++i) {int u = read(), v = read(), w = read();con(u, v, w);}int s = min(7, n);d[s] = 1;dfs(s);long long ans = 0;for (int i = 1; i <= n; ++i)add(w[i]);for (int i = 1; i <= n; ++i)ans = max(ans, find(w[i]));cout << ans;return 0;
}

这是我的第二十篇文章，如有纰漏也请各位大佬指正
辛苦创作不易，还望看官点赞收藏打赏，后续还会更新新的内容。