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 ightarrow 1)(1 ightarrow 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 最长异或路径

题目链接

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

为什么呢??

根据异或的性质,在(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
",maxx);
	return 0;
}
原文地址:https://www.cnblogs.com/last-diary/p/11469641.html