Trie树之最大异或对问题
这是C++算法基础-数据结构专栏的第二十八篇文章，专栏详情请见此处。
从这篇博客开始，文章将会于每周一更新，望周知！
引入
上次，我们学习了Trie树之字符串统计问题，字符串统计问题中的Trie树节点存储的是字符，而在最大异或对问题中，Trie树则存储了二进制数字。
下面我们就来讲Trie树之最大异或对问题的实现。
定义
最大异或对问题指的是给定若干个整数，选出两个进行xor（异或）运算，求出最大的可能的结果。
过程
例题
题目大意：给定若干个整数，让你从中选出两个进行xor（异或）运算，得到的结果最大是多少？
算法
Trie树的基本结构我已经在上篇文章中讲解了，如果想了解具体内容，可以移步至我的这篇博客：Trie树之字符串统计问题。关于异或运算的详细讲解我在位运算的实现提到过，有兴趣的小伙伴可以去学习~
先思考这样一个问题，在异或运算中，如何才能得到最大值呢？对于一个二进制数位，或者
，所以两个不同的二进制数位异或才能得到最大值
。把这一结论推广到一个二进制数字，只需要从最高位开始，根据每一位上的数尽可能地找到所对应不同的二进制数位进行异或。
有了这样的思路，我们就想到用Trie树储存，具体来说就是在每个节点上存储一个二进制数位，这样一条路径就是一个二进制数了。对于本题，我们遍历所有的二进制数，寻找最大异或对，记录最大值即可。
代码
下面给出Trie树之最大异或对问题的实现代码：
int n,a[N],son[M][2],idx,res;
void insert(int x){
int p=0;
for(int i=30;i>=0;i--){
int &s=son[p][x>>i&1];
if(!s) s=++idx;
p=s;
}
}
int search(int x){
int p=0,res=0;
for(int i=30;i>=0;i--){
int s=x>>i&1;
if(son[p][!s]){
res+=1<<i;
p=son[p][!s];
}
else p=son[p][s];
}
return res;
}上一篇-Trie树之字符串统计问题 C++算法基础专栏文章 下一篇-并查集的实现
每周一更新一篇文章，内容一般是自己总结的经验或是在其他网站上整理的优质内容
点个赞，关注一下呗~
原文地址：https://blog.csdn.net/wyuchen123/article/details/142031636
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！