题目描述
在给定的 N 个整数 A1,A2……AN 中选出两个进行 xor(异或)运算,得到的结果最大是多少?
输入格式
第一行输入一个整数 N。
第二行输入 N 个整数 A1~AN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤105,
0≤Ai<231
输入样例:
3
1 2 3
输出样例:
3
区别:
写法一:search函数直接求最大异或值
写法二:query函数先求最大异或值的那个被异或的值,然后在主函数中再求一遍异或
比如:a ^ b = c
前者求c
后者求b
写法一
#include<iostream>
using namespace std;
const int N = 100010, M = 3100010; //每位数31位,共10万个数据
int son[M][2], a[N], idx;
int n;
//插入数据
void insert(int x)
{
int p = 0;
for(int i = 30; ~ i; i -- ) //~ i 等价于 i >= 0, 因为~0=-1
{
//&是引用, s是son的别名,一个变两个都变, 使得代码更简洁
int &s = son[p][x >> i & 1];
if(!s) s = ++ idx; //如果不存在这个结点,则生成一个并指向下一个结点
p = s; //这里不能画蛇添足加个else,因为两种情况都需要p更新
}
}
//查找数据x最大的异或值
int search(int x)
{
int p = 0, res = 0;
for(int i = 30; ~ i; i -- )
{
int u = x >> i & 1; //右移i位 并与1 取与,显示x的二进制第i位0或1数字
if(son[p][!u]) //如果与原位相反的位存在(保证最大异或值),则沿着这个结点走下去
{
res += 1 << i; //更新最大异或值,这里必定是1,else那边必定是0,因为用到了左移运算符,所以else那边没有加的必要了
p = son[p][!u]; //更新p
}
else p = son[p][u]; //否则从原结点走下去,并更新p
}
return res;
}
int main()
{
scanf("%d", &n);
int res = 0;
for(int i = 0; i < n; i ++ )
{
scanf("%d", &a[i]);
insert(a[i]);
res = max(res, search(a[i]));
}
printf("%d", res);
return 0;
}
写法二
#include<iostream>
using namespace std;
const int N = 100010, M = 3100010;
int son[M][2], a[N], idx;
int n;
//向Tire树中插入数据
void insert(int x)
{
int p = 0;
for(int i = 30; i >= 0; i -- )
{
int u = x >> i & 1;
if(!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
}
//查询每一个数据x的最大异或值的那个被异或的数据res
int query(int x)
{
int p = 0, res = 0;
for(int i = 30; i >= 0; i -- )
{
int u = x >> i & 1;
if(son[p][!u])
{
res = res * 2 + !u; //更新被异或的数据res
p = son[p][!u];
}
else
{
res = res * 2 + u; //if和else两种情况里的u都有可能是0或1
p = son[p][u];
}
}
return res;
}
int main()
{
scanf("%d", &n);
int res = 0;
for(int i = 0; i < n; i ++ )
{
scanf("%d", &a[i]);
insert(a[i]);
//因为query函数求的是被异或值,所以这里求最大异或值还得与a[i]异或以一下
res = max(res, a[i]^query(a[i]));
}
printf("%d", res);
return 0;
}