刚刚补了前天的CF的D题再做这题感觉轻松了许多。简直一个模子啊。。。跑树上异或x最大值。贪心地让某位的值与x对应位的值不同即可。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 #define CLR(a,b) memset((a),(b),sizeof((a))) 7 using namespace std; 8 typedef long long ll; 9 const int N = 32; 10 const int M = 1e5+5; 11 int n, m; 12 struct Trie { 13 int next[2]; 14 int v; 15 void init() { 16 v = 0; 17 memset(next, -1, sizeof(next)); 18 } 19 }T[N*M*2]; 20 int le; 21 void inser(int x) { 22 int p = 0; 23 for(int i = N-1; i >= 0; --i) { 24 int t = (x>>i) & 1; 25 if(T[p].next[t] == -1) { 26 T[le].init(); 27 T[p].next[t] = le++; 28 } 29 p = T[p].next[t]; 30 } 31 T[p].v = x; 32 } 33 void query(int x) { 34 int i = 0, p = 0; 35 for(int i = N-1; i >= 0; --i) { 36 int t = ((x>>i) & 1); 37 if(T[p].next[t^1] == -1) p = T[p].next[t]; 38 else p = T[p].next[t^1]; 39 } 40 printf("%d ", T[p].v); 41 } 42 int main() { 43 int t, i, x; 44 scanf("%d", &t); 45 for(int k = 1; k <= t; ++k) { 46 printf("Case #%d: ", k); 47 scanf("%d%d", &n, &m); 48 le = 1; T[0].init(); 49 for(i = 1; i <= n; ++i) {scanf("%d", &x); inser(x);} 50 while(m--) { 51 scanf("%d", &x); 52 query(x); 53 } 54 } 55 return 0; 56 }