XiYuJing|文章:最大异或对

[[ slide_text ]]

[[item.c]]

最大异或对

发布时间：2022年10月08日 作者：靖华来源：XiYuJing

算法 C++ Trie

# 最大异或对
## 题目
在给定的 N 个整数 A1，A2……AN 中选出两个进行 **xor**（异或）运算，得到的结果最大是多少？

输入格式
第一行输入一个整数 N。

第二行输入 N 个整数 Ai~AN。

输出格式
输出一个整数表示答案。

数据范围
1 ≤ N ≤ 105
0 ≤ A i < 231
输入样例：
```
3
1 2 3
```
输出样例：
```
3
```

>题目来源于AcWing

## 代码
```
#include<iostream>
#include<cstring>
#include<algorithm>
#define ios ios::sync_with_stdio(false),cout.tie(0),cin.tie(0)
using namespace std;
const int N =3e6;
int a[N],p[N][2],idx=1;
void inset(int s)
{
 int x = 0;
 for(int i=30;i>=0;i--)
 {
 // int y = p[x][s>>i&1]; 
 // if(!y)p[x][s>>i&1]=idx++;
 // x=p[x][s>>i&1];
		//上下两个是等价的，但是更简洁
 int &y = p[x][s>>i&1];
 if(!y)y=idx++;
 x=y;
 }
}
int search(int s)
{
 int x=0,res=0;
 for(int i=30;i>=0;i--)
 {
 int y = s>>i&1;
 if(p[x][!y])
 {
 res +=1<<i;
 x= p[x][!y];
 }
 else{
 x = p[x][y];
 }
 }
 return res;
}
int main()
{
 ios;
 int n;
 cin>>n;
 for(int i=0;i<n;i++)
 {
 cin>>a[i];
 inset(a[i]);
 }
 int m=0;
 for(int i=0;i<n;i++)m = max(m,search(a[i]));
 cout<<m<<endl;
}
```

你觉得文章怎么样

已浏览 106 次，0 条评论