问题 D: 异或最大值

时间限制: 1 Sec 内存限制: 128 MB
提交: 116 解决: 52

题目描述

给定一些数，求这些数中两个数的异或值最大的那个值

输入

多组数据。第一行为数字个数n，1 <= n <= 10 ^ 5。接下来n行每行一个32位有符号非负整数。

输出

任意两数最大异或值

样例输入

3 3 7 9

样例输出

14

可能这类题型接触不多，再加上一些运算符的概念也不清楚，开始看别人的参考代码很久都没理解，但认真啃下去还是总算理解了它的奥妙之处~~所以才打算记录这个典型的01字典树题型。

运算符的概念可以参考我这篇 C语言移位运算符(＜＜,＞＞)、按位与(&)、按位或( | )、异或( ^ 、xor )的简单认识

---

思路：如果用暴力直接比较，很明显会超限。得想到用01字典树贪心解决。

先把每个值转成二进制后放进字典树中，最后再进行比较。因为是求最大异或值，先从高位开始比较，如果它相反的情况满足，则直接跳转该节点，以此下去，找到它所满足的对应值，再跟它进行异或得出它所满足的最大异或值，最后再跟已记录的最大异或值比较。

参考代码

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define N 100005
int node[N][2]; //记录每个节点的左右孩子 
int value[N]; //记录每个节点保存的值 ，  当然node和value也可以放在一个结构体里
int sum; //记录总共的节点数 ， sum对应的就是每次建树过程的N，当时这里我一直没能想过来 
int maxn;

void init()  //初始化 
{
	sum=1;  //总数需从1开始，如果从0的话 node[N][2] 这里会有节点被记为 0 ，会导致误判。除非 line 26 改为 ++sum 
	maxn=0;
	memset(value,0,sizeof(value));
	memset(node,0,sizeof(node));	
 } 
 
void build(int a)   //建立 01 字典树 
{
	int now=0;
	for(int i=31;i>=0;i--)  //根据题目要求32位，则从32位最左边位数开始建立 
	{
		int bits = (a>>i)&1;  //右移按位与，得出每个二进位 
		if(!node[now][bits])   
		{
			node[now][bits]=sum++;
		}
		now = node[now][bits];
	}
	value[now]=a;
}

void search(int a)  //贪心查找 
{
	int now=0;
	for(int i=31;i>=0;i--)
	{
		int bits = (a>>i)&1;  
		if(node[now][bits^1])   //此处用到贪心，因为从最高位开始比较，要获得最大异或值，如果它相反的情况满足，则直接前往。 
		{
			now = node[now][bits^1];
		}else
		{
			now = node[now][bits];
		}
		
	 }
	maxn = max(maxn,a^value[now]);  //找到最大满足值后与a异或得出该a的最大异或值，再与maxn比较 
}

int main()
{
	int n;
	while(cin>>n)
	{
		int a[n];
		init();
		for(int i=0;i<n;i++)
		{
			cin>>a[i];
			build(a[i]);	
		}
		for(int i=0;i<n;i++)
		{
			search(a[i]);   //这行其实可以直接放在build下面。
		}
		cout<<maxn<<endl;
	}
	return 0;
 }