The XOR Largest Pair（算法竞赛进阶指南 P72，Trie）

本文主要是介绍The XOR Largest Pair（算法竞赛进阶指南 P72，Trie），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一.题目链接：

The XOR Largest Pair

二.题目大意：

有 n 个数，求任意两个数异或得到的最大值.

三.分析：

刚学习了字典树，觉得还不错.

把每个数分解为二进制存到字典树中，查询即可.

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-8
#define lc k * 2
#define rc k * 2 + 1
#define pi acos(-1.0)
#define ll long long
#define ull unsigned long long
using namespace std;const int M = (int)1e5;
const int mod = 99991;
const int inf = 0x3f3f3f3f;int x, ans = -inf;
int cnt = 1;
int trie[M * 50 + 5][2];void Insert()
{int p = 1;for(int i = 30; i >= 0; --i){bool v = (x>>i) & 1;if(!trie[p][v])trie[p][v] = ++cnt;p = trie[p][v];}
}int Query()
{int p = 1;int res = 0;for(int i = 30; i >= 0; --i){int v = (x>>i) & 1;if(trie[p][!v]){res |= (1<<i);p = trie[p][!v];}elsep = trie[p][v];}return res;
}int main()
{int n;scanf("%d", &n);while((n--) > 0){scanf("%d", &x);ans = max(ans, Query());Insert();}printf("%d\n", ans);return 0;
}

 

这篇关于The XOR Largest Pair（算法竞赛进阶指南 P72，Trie）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---