CH1602:The XOR Largest Pair 题解

主要思路

如何找到一对异或值最大的数字呢？我们先从二进制计算（位运算）本身讲起，如果我们要保证$Xor$值更大，那么我们就需要尽可能多的$1$，除此之外，$1$的位置也非常重要，在一些情况下靠前更好。我们可以考虑从最高位为起点向最低位建立一个 Trie 树。我们记$num[i]$表示第$i$位的$0或1$状态。建立 Trie 树之后，我们计算出每个数所对应的异或值最大的值。我们的策略是：

• 我们已经从第 30 位移动到第 $i$ 位了，我们期望的对应的数位是$1\; xor \; 1$，如果在节点上有这个值，那么正常向下递归。
• 如果没有我们期望的数字，那么我们只能选同位数了，向下递归时要注意端点和上一条不一样。

具体的请看代码：

代码

	// CH1602.cpp
	#include <iostream>
	#include <cstdio>
	using namespace std;
	const int maxn = 100000 * 40;
	int trie[maxn][2], arr[maxn], n, current = 2;
	void insert(int num)
	{
	int pnode = 1;
	for (int i = 30; i >= 0; i--)
	{
	int bit = (num >> i) & 1;
	if (trie[pnode][bit] == 0)
	trie[pnode][bit] = current++;
	pnode = trie[pnode][bit];
	}
	}
	int getBiggest(int num)
	{
	int ans = 0, pnode = 1;
	for (int i = 30; i >= 0; i--)
	{
	int bit = (num >> i) & 1;
	if (trie[pnode][bit ^ 1] != 0)
	pnode = trie[pnode][bit ^ 1], ans |= (1 << i);
	else
	pnode = trie[pnode][bit];
	}
	return ans;
	}
	int main()
	{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	scanf("%d", &arr[i]), insert(arr[i]);
	int ans = 0;
	for (int i = 0; i < n; i++)
	ans = max(ans, getBiggest(arr[i]));
	printf("%d", ans);
	return 0;
	}

view raw CH1602.cpp hosted with by GitHub