codevs3031 最富有的人

题目描述 Description

在你的面前有n堆金子，你只能取走其中的两堆，且总价值为这两堆金子的xor值，你想成为最富有的人，你就要有所选择。

输入描述 Input Description

第一行包含两个正整数n，表示有n堆金子。
第二行包含n个正整数，表示每堆金子的价值。

输出描述 Output Description

第一行包含一个正整数，表示能获得的最大总价值。

样例输入 Sample Input

10
1 2 3 4 5 6 7 8 9 10

样例输出 Sample Output

数据范围及提示 Data Size & Hint

数据范围：
n<=100000 每堆金子数<=2^31-1

正解：贪心+trie

解题报告：

　　以前我出的题目里面有这道题。模型抽象出来也是求两个数的xor和最大值。

　　就是把所有数插入到Trie树中，每个结点都表示的是一个二进制位，然后对于每个数再在Trie树中去查询。因为是xor，所以每一位都尽可能不同，贪心地从高位往低位选取就可以了。

 1 //It is made by jump~
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <algorithm>
 8 #include <ctime>
 9 #include <vector>
10 #include <queue>
11 #include <map>
12 #include <set>
13 using namespace std;
14 typedef long long LL;
15 const int MAXN = 100011;
16 int n,a[MAXN],cnt,ans;
17 int tr[3000000][2];
18 
19 inline int getint()
20 {
21        int w=0,q=0; char c=getchar();
22        while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar(); 
23        while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w;
24 }
25 
26 inline void insert(int x){
27     int u=1;
28     for(int i=30;i>=0;i--) {
29     int now=(x>>i)&1;
30     if(!tr[u][now]) tr[u][now]=++cnt;
31     u=tr[u][now];
32     }
33 }
34 
35 inline void query(int x){
36     int u=1; int total=0;
37     for(int i=30;i>=0;i--) {
38     int now=(x>>i)&1;
39     if(!tr[u][now^1]) u=tr[u][now];
40     else u=tr[u][now^1],total|=(1<<i);
41     }
42     ans=max(ans,total);
43 }
44 
45 inline void work(){
46     n=getint(); for(int i=1;i<=n;i++) a[i]=getint();
47     cnt=1; 
48     for(int i=1;i<=n;i++) insert(a[i]);
49     for(int i=1;i<=n;i++) query(a[i]);
50     printf("%d",ans);
51 }
52 
53 int main()
54 {
55   work();
56   return 0;
57 }