HDU 4825 Xor Sum（字典树）

嗯...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4825

这道题更明确的说是一道01字典树，如果ch[u][id^1]有值，那么就向下继续查找/建树，如果没有则向别的方向建树，类似一个贪心的思想。

每次记录一下每个节点的编号及所代表的值。

AC代码：

 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:
", i);
46         for(int k = 1; k <= m; k++){
47             long long x;
48             scanf("%lld", &x);
49             printf("%lld
", query(x));
50         }
51     }
52     return 0;
53 }

AC代码