HDU 4825 Xor Sum（字典树）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 
 5 using namespace std;
 6 
 7 int ch[3200005][3];
 8 int cnt;
 9 int val[3200005];
10 
11 inline void build(long long x){
12     int u = 0;
13     for(int i = 31; i >= 0; i--){
14         int id = (x >> i) & 1;
15         if(ch[u][id] == 0) ch[u][id] = ++cnt;
16         u = ch[u][id];
17     }
18     val[u] = x;
19 }
20 
21 inline long long query(long long x){
22     int u = 0;
23     for(int i = 31; i >= 0; i--){
24         int id = (x >> i) & 1;
25         if(ch[u][id^1]) u = ch[u][id^1];
26         else u = ch[u][id];
27     }
28     return val[u];
29 }
30 
31 int main(){
32     int t;
33     scanf("%d", &t);
34     for(int i = 1; i <= t; i++){
35         memset(ch, 0, sizeof(ch));
36         cnt = 0;
37         memset(val, 0, sizeof(val));
38         int n, m;
39         scanf("%d%d", &n, &m);
40         for(int j = 1; j <= n; j++){
41             long long x;
42             scanf("%lld", &x);
43             build(x);
44         }
45         printf("Case #%d:\n", i);
46         for(int k = 1; k <= m; k++){
47             long long x;
48             scanf("%lld", &x);
49             printf("%lld\n", query(x));
50         }
51     }
52     return 0;
53 }