The XOR Largest Pair(tire树)

题目

解析

一年前听学长讲这道题，什么01trie，好高级啊，所以没学，现在一看。。。。

看到xor就应该想到二进制，一看数据\(A_i< 2^{31}\)，考虑把所有的数都处理成长度为32的二进制数，插入字典树中，查询的时候就逐位比较，有不同的先走不同的那边，这样保证了每次插入一个数时查询的结果是最大的，然后不断更新最大值就可以了

我这种不用位运算的懒人就直接用bitset维护了

从高位到地位插入可能好算一些

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 4e6 + 10;

int n, a, num, ans;

struct node {

	int nx[2];

} e[N];

void insert(int n) {

	bitset<35>s(n);

	int rt = 0;

	for (int i = 30; i >= 0; --i) {

		int v = (int)s[i];

		if (!e[rt].nx[v]) e[rt].nx[v] = ++num;

		rt = e[rt].nx[v];

	}

}

int query(int x) {

	bitset<35>s(x);

	int rt = 0, ret = 0;

	for (int i = 30; i >= 0; --i) {

		int v = (int)s[i];

		if (e[rt].nx[v ^ 1]) ret = ret << 1 | 1, rt = e[rt].nx[v ^ 1];

		else ret <<= 1, rt = e[rt].nx[v];

	}

	return ret;

}

int main() {

	cin >> n;

	for (int i = 1, x; i <= n; ++i) {

		cin >> x;

		ans = max(ans, query(x));

		insert(x);

	}

	cout << ans;

}

巴特西

The XOR Largest Pair(tire树)

题目

解析

代码

最新文章

热门文章