本文主要是介绍CH 1602 The XOR Largest Pair 字典树+异或，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：http://contest-hunter.org:83/contest/0x10%E3%80%8C%E5%9F%BA%E6%9C%AC%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E3%80%8D%E4%BE%8B%E9%A2%98/1602%20The%20XOR%20Largest%20Pair
描述
在给定的N个整数A1，A2……AN中选出两个进行xor运算，得到的结果最大是多少？
输入格式
第一行一个整数N，第二行N个整数A1～AN。
输出格式
一个整数表示答案。
样例输入
3
1 2 3样例输出
3数据范围与约定
- 对于100%的数据: N<=10^5, 0<=Ai<2^31
算法分析：
题目要求寻找2个数异或的最大值，我们把每个整数看做长度为32的二进制的01串（数值较小的时候前面补0），并把A1---Ai-1（注意这里i是动态的，没一次Ai放进去之前都要查询一遍）对应的32位二进制串插入一颗Trie树（其中最低二进制位位叶子节点）。然后，关键是字典树查询代码，我们可以由异或的性质的知道，不同为1，相同为0，所以我们在查询的时候要贪心的寻找不同的，如果实在不通再按照原路线走。
代码有二进制对应的作用
代码实现：
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxnode=1000000+100;
const int sigma_size=35;
struct Trie
{int ch[maxnode][sigma_size];int sz;void init(){sz=1;memset(ch[0],0,sizeof(ch[0]));}void insert(int x){int u=0;for(int i=31;i>=0;i--){int id=(x>>i)&1;//取出x二进制第i位if(ch[u][id]==0){ch[u][id]=sz;memset(ch[sz],0,sizeof(ch[sz]));sz++;}u=ch[u][id];}}int find(int x){int ans=0,u=0;for(int i=31;i>=0;i--){int id=(x>>i)&1;int y=id^1; //找与id不同的if(ch[u][y]==0){u=ch[u][id];ans<<=1; //相同为0,ans=ans*2}else{u=ch[u][y];ans=ans<<1|1; //不同为1,ans=ans*2+1 }}return ans;}
};
Trie trie;
int main()
{trie.init();int maxx=0;int n;scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);maxx=max(maxx,trie.find(x));trie.insert(x);}cout<<maxx<<endl;return 0;
}
这篇关于CH 1602 The XOR Largest Pair 字典树+异或的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
