刚刚补了前天的CF的D题再做这题感觉轻松了许多。简直一个模子啊。。。跑树上异或x最大值。贪心地让某位的值与x对应位的值不同即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define CLR(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long ll;
const int N = ;
const int M = 1e5+;
int n, m;
struct Trie {
int next[];
int v;
void init() {
v = ;
memset(next, -, sizeof(next));
}
}T[N*M*];
int le;
void inser(int x) {
int p = ;
for(int i = N-; i >= ; --i) {
int t = (x>>i) & ;
if(T[p].next[t] == -) {
T[le].init();
T[p].next[t] = le++;
}
p = T[p].next[t];
}
T[p].v = x;
}
void query(int x) {
int i = , p = ;
for(int i = N-; i >= ; --i) {
int t = ((x>>i) & );
if(T[p].next[t^] == -) p = T[p].next[t];
else p = T[p].next[t^];
}
printf("%d\n", T[p].v);
}
int main() {
int t, i, x;
scanf("%d", &t);
for(int k = ; k <= t; ++k) {
printf("Case #%d:\n", k);
scanf("%d%d", &n, &m);
le = ; T[].init();
for(i = ; i <= n; ++i) {scanf("%d", &x); inser(x);}
while(m--) {
scanf("%d", &x);
query(x);
}
}
return ;
}
343ms