vodevs3031 最富有的人-白红宇

vodevs3031 最富有的人

阅读量：6250 次

发布时间：2019-06-22

本文共 1329 字，大约阅读时间需要 4 分钟。

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

输入描述

Input Description

第一行包含两个正整数n，表示有n堆金子。

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

输出描述

Output Description

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

样例输入

Sample Input

1 2 3 4 5 6 7 8 9 10

样例输出

Sample Output

数据范围及提示

Data Size & Hint

数据范围：

n<=100000 每堆金子数<=2^31-1

题解:

这道题,显然我们是要区两个异或的最大值，对于一个数，如果我们选择的另一个数二进制数位差距

越大，显然得到的结果更大，所以我们可以考虑把每个数的二进制数位存下来，用字典树来实现，

具体先枚举一个数，然后跑字典树，当然每一步尽量走相反的路线，那么得到的值对于这个数就是

最优的，然后取个MAX就可以了。

代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 using namespace std;typedef long long LL;const int MAXN = 100011;int n,a[MAXN],cnt,ans;int tr[3000000][2];inline int getint(){ int w=0,q=0; char c=getchar(); while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar(); while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w; } inline void insert(int x){ int u=1; for(int i=30;i>=0;i--) { int now=(x>>i)&1; if(!tr[u][now]) tr[u][now]=++cnt; u=tr[u][now]; } } inline void query(int x){ int u=1; int total=0; for(int i=30;i>=0;i--) { int now=(x>>i)&1; if(!tr[u][now^1]) u=tr[u][now]; else u=tr[u][now^1],total|=(1<