【HDU 5536】2015 ACM-ICPC 长春 Chip Factory 01字典树

有一个数组,让你选取三个数,使其中两个数相加异或上另外一个数值最大。

很明显的异或最大要用01字典树,问题是要选取三个数。我们可以提前把所有的数字插入到01字典树上,每次枚举其中两个数时,先在字典树上面删除这两个数,然后再查询。问题又来了,我们怎么删除了,因为我们用的是公共前缀,所以我们可以对01字典树上的边进行计数,每次插入 +1,删除 -1,如此就可以完成删除操作了。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 7; // 插入字符串个数
typedef long long ll;
const ll inf = 1e5;
int ch[maxn * 32][2], sz; // 边
ll val[maxn * 32];  // 点
ll a[maxn], num[maxn * 32]; // num 记录每条边的使用次数 
void init() // 初始化
{
	sz = 1;  // 根结点
	memset(ch, 0, sizeof(ch));
	memset(num, 0, sizeof(num));
}
void insert(ll x)  // 插入
{
	int u = 0;
	for(int i = 32; i >= 0; i--) {
		int v = (x >> i) & 1;
		if(ch[u][v]) num[ch[u][v]] ++; // 如果已经有了 边的访问次数+1
		if(!ch[u][v]) {
			ch[u][v] = sz++;
			num[ch[u][v]] ++;
			val[ch[u][v]] = 0;
		}
		u = ch[u][v];
	}
	val[u] = x;
}
void delete1(ll x)  // 删除
{
	int u = 0;
	for(int i = 32; i >= 0; i--) {
		int v = (x >> i) & 1;
		num[ch[u][v]]--;  // 只需要把走的边的次数-1
		u = ch[u][v];
	}
}
ll query(ll x)  // 查询
{
	int u = 0;
	for(int i = 32; i >= 0; i--) {
		int v = (x >> i) & 1;
		if(ch[u][v^1] && num[ch[u][v^1]] > 0) u = ch[u][v^1];  // 贪心选择不同的
		else u = ch[u][v];
	}
	return val[u];
}
int main()
{
	int t, n;
	scanf("%d", &t);
	while(t--) {
		init();
		scanf("%d", &n);
		for(int i = 0; i < n; i++) {
			scanf("%lld", &a[i]);
			insert(a[i]);
		}
		ll maxx = -inf;
		int x, y;
		for(int i = 0; i < n; i++) {
			delete1(a[i]);
			for(int j = i + 1; j < n; j++) {
				delete1(a[j]);
				ll ans = query(a[i] + a[j]);
				if((ans ^ (a[i] + a[j])) > maxx) maxx = (ans ^ (a[i] + a[j]));
				insert(a[j]);
			}
			insert(a[i]);
		}
		printf("%lld\n", maxx);
	}
	return 0;
}

 

上一篇:内存对齐的目的


下一篇:flutter chip标签组件