ACWing 最大异或对 Trie

ACWing 最大异或对 Trie

题目很简答，但是暴力肯定是过不了的

暴力中有什么优化呢

外层遍历ai，内层的j从0到i- 1遍历，即每次只遍历ai之前的数与ai相异或，然后取最大值

那么还可以怎么优化呢？这里当然是用到Trie：

1.0 < Ai < 2^31, 这里用二进制来实现，取二进制的每一位（0或1）；要注意的是，如果Ai < 2^n, 例如想一下，Ai < 2^2, 即Ai可以取0到3，那么也就是有两个位数，用Ai << k的时候k应该取0和1；

所以Ai < 2^31, 最大的数有31个位数，所以k取0到31；因为想要使异或之后的数取大，所以应该从最高位开始看起；

2.res最小值为0，Ai^Ai也为0，所以先插入Ai，再访问它前面插入的数和Ai并没有影响；

3.一个数有31个位数，最大1e5个数，所以最多最多有3100000个节点，所以son[N][2]的节点数开3100000，这个数组“2”的意思是一个节点可以有两个子节点（0/1）；

4.对!u的理解：

我试了一下发现，如果u = 0, !u 就为1；

其他任何不为0的数，!u为0；

这个地方的意思就是，如果这一位为1，就看看这个节点这有没有为0的节点（如果为0，就看有没有1），有这个节点就取这个节点，并把p变成这个节点的idx，如果没有，就只能取u了，并且子节点是这个节点；

5.不要学混了，最近学了并查集和Trie，并查集更注重于根节点，所以有路径压缩；但是Trie更注重的是父节点而不是根节点，它要通过这个父节点找到它的子节点，所以这里要注意，不要想偏了，不需要有p[x]数组；

6.多练习，继续加油！

AC代码：

#include
#include
#include
#include
#include
#include
using namespace std;
#define INF 0x3f3f3f3f
typedef pair PII;
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for (int i = m; i >= (1); --i)
typedef long long ll;

const int N = 3100000;
int son[N][2], idx = 0;

void insert(int x) {
	int p = 0;
	for (int i = 30; i >= 0; i--) {
		int u = (x >> i) & 1;
		if (!son[p][u]) son[p][u] = ++idx;
		p = son[p][u];
	}
}

int search(int x) {
	int p = 0, res = 0;
	for (int i = 30; i >= 0; i--) {
		int u = (x >> i) & 1;
		if (son[p][!u]) {
			res = (res << 1) + !u;
			p = son[p][!u];
		}
		else {
			res = (res << 1) + u;
			p = son[p][u];
		}
	}
	return res;
}

int main() {
	int n, t;
	cin >> n;
	int res = 0;
	for (int i = 0; i < n; i++) {
		cin >> t;
		insert(t);
		int k = search(t);
		res = max(res, t ^ k);
	}
	cout << res << endl;
	return 0;
}