01Trie学习笔记

矫情吗；* 2023-06-01 15:54 22阅读 0赞

### \\(01Trie\\)学习笔记 ###

#### 前置知识： ####

##### \\(Trie\\)树 #####

##### \\(xor\\)的一些性质 #####

*  \\(xor\\)对于\\(0\\)和\\(1\\)，两个数相同返回\\(0\\)，不同返回\\(1\\)

所以我们可以得到一些很有意思的结论

1.  \\\[0\\ xor\\ 1\\ =\\ 1\\\]
2.  \\\[1\\ xor\\ 1\\ =\\ 0\\\]
3.  \\\[p\\ xor\\ p\\ =\\ 0\\\]
4.  \\\[p\\ xor\\ 0\\ =\\ p\\\]

根据第\\(1\\)和\\(2\\)条我们可以用\\(xor\\ 1\\)来实现\\(0\\rightarrow 1\\)，\\(1\\rightarrow 0\\)的操作

*  自反性

\\\[a\\ xor\\ b\\ =\\ c \\\]

\\\[c\\ xor\\ b\\ = \\ a \\\]

##### \\(and\\)的一些性质 #####

*  \\(and\\)对于\\(0\\)和\\(1\\)，只有两个数都是\\(1\\)返回\\(1\\),其余返回\\(0\\)

--------------------

相信大家都知道\\(Trie\\)树,\\(01Trie\\)其实就是对数的二进制位进行建\\(Trie\\)树，它被用来处理一些和\\(xor\\)有关的问题。

首先是建树部分就是每一个要插入的数转化为二进制的\\(01\\)串，然后按从低位或从高位建树（取决于题目），注意\\(01Trie\\)的信息是存在节点上的但实际是存在边上的。

从高位建树

int rt=0; for (int i=maxsize;i;i>>=1) { bool x=val&i; if (!ch[rt][x]) ch[rt][x]=++cnt; rt=ch[rt][x]; }

其中\\(maxsize\\)是大于最大数的\\(2^n\\)，这样就相当于每次都将一个\\(1\\)往低位移动，然后根据\\(and\\)的性质就可以判断这一位是\\(0\\)还是\\(1\\)。

[\\(P4551\\) 最长异或路径][P4551_]

这道题目，只需要从根节点把到每个点的异或和都求一下，然后再在这些数中找两个异或起来最大的数就可以了。

为什么呢？？

根据异或的性质，在\\(LCA\\)以上边权会抵消不会影响答案。

然后我们从高位开始贪心，因为高位的一个\\(1\\)显然比低位的优。

怎样贪心呢？？

我们想尽量让它返回\\(1\\)，所以我们只需要判断是否有当前位异或\\(1\\)的节点就可以了。

#include<iostream> #include<cstdio> using namespace std; const int N=1e5+100,maxsize=1<<30; struct edge{ int s,e,v,net; }ed[N<<1]; int cnt; struct Tire{ int ch[N<<5][2]; inline void add(int val) { int rt=0; for (int i=maxsize;i;i>>=1) { bool x=val&i; if (!ch[rt][x]) ch[rt][x]=++cnt; rt=ch[rt][x]; } } inline int query(int val) { int ans=0,rt=0; for (int i=maxsize;i;i>>=1) { bool x=val&i; if (ch[rt][x^1]) { ans=(ans<<1)|(x^1); rt=ch[rt][x^1]; } else { ans=(ans<<1)|x; rt=ch[rt][x]; } } return ans; } }T; int n,tot; int head[N],val[N]; inline void dfs(int x,int fa) { for (int i=head[x];i;i=ed[i].net) if (ed[i].e!=fa) { val[ed[i].e]=val[x]^ed[i].v; dfs(ed[i].e,x); } return ; } inline void add(int s,int e,int v) { ed[++tot]=(edge){s,e,v,head[s]}; head[s]=tot; return ; } int main() { scanf("%d",&n); for (int i=1;i<=n-1;i++) { int s,e,v; scanf("%d%d%d",&s,&e,&v); add(s,e,v);add(e,s,v); } dfs(1,0); for (int i=1;i<=n;i++) T.add(val[i]); int maxx=0; for (int i=1;i<=n;i++) maxx=max(T.query(val[i])^val[i],maxx); //因为01Tire求的是让这个数异或的最大值的异或值，所以还要异或回来 printf("%d\n",maxx); return 0; }

转载于:https://www.cnblogs.com/last-diary/p/11469641.html

[P4551_]: https://www.luogu.org/problem/P4551