HDU 4825:Xor Sum(Trie)

时间:2022-04-27 22:45:46

http://acm.hdu.edu.cn/showproblem.php?pid=4825

题意:给出N个数,M个询问,每个询问给出一个X,问在这N个数中哪个数和X异或后结果最大。

思路:可以用Trie构造出sigmaSize为0和1的点,先将N个数插入Trie,然后询问在Trie上尽量找可以不同的数,不同的话异或起来是最大的。

 #include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
#define N 2000010
int a[];
struct Trie
{
int ch[N][], num; //注意节点数要开大,因为每个N可能有很多个节点
int val[N];
void init()
{
num = ;
memset(ch[], , sizeof(ch[]));
} void Update(int x, int id)
{
int u = ;
for(int i = ; i >= ; i--) {
int v = (( << i) & x) > ? : ;
if(!ch[u][v]) {
memset(ch[num], , sizeof(ch[num]));
val[num] = ;
ch[u][v] = num++;
}
u = ch[u][v];
}
val[u] = id;
} int Query(int x)
{
int u = ;
for(int i = ; i >= ; i--) {
int v = (( << i) & x) > ? : ;
v = !v;
if(ch[u][v]) {
u = ch[u][v];
} else{
u = ch[u][!v];
}
}
return val[u];
}
}trie; int main()
{
int t;
scanf("%d", &t);
for(int cas = ; cas <= t; cas++) {
int n, m;
scanf("%d%d", &n, &m);
trie.init();
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
trie.Update(a[i], i);
}
printf("Case #%d:\n", cas);
for(int i = ; i <= m; i++) {
long long q;
scanf("%d", &q);
printf("%d\n", a[trie.Query(q)]);
}
}
return ;
}