首页 > 代码库 > hdu 4825 Xor Sum （建树） 2014年百度之星程序设计大赛 - 资格赛 1003

hdu 4825 Xor Sum （建树） 2014年百度之星程序设计大赛 - 资格赛 1003

2024-07-05 11:54:46   221人阅读

题目

题意：给n个数，m次询问，每次给一个数，求这n个数里与这个数 异或 最大的数。

思路：建一个类似字典数的数，把每一个数用 32位的0或者1 表示，查找从高位向底位找，优先找不同的，如果没有不同的，就找相同的。 

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 #define LL long long
 7 const int maxn = 3200000;
 8 int p[maxn][2], cnt; //cnt代表序号，<= maxn
 9 __int64 val[maxn];
10 
11 void init()
12 {
13     memset(p, 0, sizeof(p));
14     cnt = 1;
15 }
16 void insert(int x)
17 {
18     int u = 0, v, i;
19     for(i = 31; i >= 0; i--)
20     {
21         v = (x&(1<<i))? 1 : 0;
22         if(!p[u][v])
23         p[u][v] = cnt++;
24         u = p[u][v];
25     }
26     val[u] = x;
27 }
28 void find(int x)
29 {
30     int u = 0, v, i;
31     for(i = 31; i >= 0; i--)
32     {
33         v = (x&(1<<i))? 1 : 0;
34         if(p[u][v^1])
35             u = p[u][v^1];
36         else
37             u = p[u][v];
38     }
39     printf("%I64d\n", val[u]);
40 }
41 int main()
42 {
43     int t, n, m, i, ca;
44     __int64 x;
45     while(~scanf("%d", &t))
46     {
47         ca = 1;
48         while(t--)
49         {
50             init();
51             scanf("%d%d", &n, &m);
52             for(i = 0; i < n; i++)
53             {
54                 scanf("%I64d", &x);
55                 insert(x);
56             }
57             printf("Case #%d:\n", ca++);
58             for(i = 0; i < m; i++)
59             {
60                 scanf("%I64d", &x);
61                 find(x);
62             }
63         }
64     }
65     return 0;
66 }

 


联系
我们