本文主要是介绍Find MaxXorSum 经典字典树求异或最大值（数据量大），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
-
题目：https://cn.vjudge.net/problem/NBUT-1597
-
[1597] Find MaxXorSum
- 时间限制: 2000 ms 内存限制: 65535 K
- 问题描述
-
Given n non-negative integers, you need to find two integers a and b that a xor b is maximum. xor is exclusive-or.
- 输入
-
Input starts with an integer T(T <= 10) denoting the number of tests.
For each test case, the first line contains an integer n(n <= 100000), the next line contains a1, a2, a3, ......, an(0 <= ai <= 1000000000); - 输出
-
For each test case, print you answer.
- 样例输入
-
2 4 1 2 3 4 3 7 12 5 - 样例输出
-
7 11 - 提示
-
无 - 来源
-
Alex@NBUT - 操作
参考解析：CH 1602 The XOR Largest Pair 字典树+异
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
const int maxnode=100000+100;
const int sigma_size=3;
struct Trie
{int ch[maxnode*13][sigma_size];//注意要多开10倍int sz;void clear(){sz=1;memset(ch[0],0,sizeof(ch[0]));}void insert(ll x){int u=0;for(int i=31;i>=0;i--){int id=(x>>i)&1;//取出第i位if(ch[u][id]==0){ch[u][id]=sz;memset(ch[sz],0,sizeof(ch[sz]));sz++;}u=ch[u][id];}}ll find(ll x){ll 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;
ll a[maxnode];
int main()
{int n;int t;cin>>t;while(t--){ ll maxx=0;trie.clear();scanf("%d",&n);for(int i=1;i<=n;i++){ll x;scanf("%lld",&x);maxx=max(maxx,trie.find(x));trie.insert(x);//cout<<i<<endl;}cout<<maxx<<endl;}return 0;
}
这篇关于Find MaxXorSum 经典字典树求异或最大值（数据量大）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
