1216: 异或最大值

Time Limit: 2 Sec 

Memory Limit: 128 MB

Submit: 98 

Solved: 29 [ ][ ][ ]

Description

给定一些数，求这些数中两个数的异或值最大的那个值

 

Input

第一行为数字个数n，1 <= n <= 10 ^ 5。接下来n行每行一个32位有符号非负整数。

 

Output

任意两数最大异或值

 

Sample Input

3379

Sample Output

14

HINT

 

这道题，我学到了一些新的知识。

没有写过字典树。这题用01字典树。

构建树，和树形dp是一样的，都是树。

思路：

　　暴力会超时。

　　用字典树，01字典树。

1 #include
     
       2 #include
      
        3 #include
       
         4  5 typedef struct 6 { 7     int a[2]; 8     int num; 9 }Tril;10 Tril f[100010<<5];11 int root,ans;12 13 void insert(int x,int u,int num)14 {15     int i,k;16     for(i=num;i>=0;i--)17     {18         k=(1<
        
         =0;i--)29     {30         k=(1<
         
          ans)38         ans=j;39 }40 int main()41 {42     int n,i,x;43     while(scanf("%d",&n)>0)44     {45         memset(f,-1,sizeof(Tril)*((n+1)<<5));46         ans=0;47         root=1;48         for(i=1;i<=n;i++)49         {50             scanf("%d",&x);51             insert(x,0,31);52              query(x,0,31);53         }54         printf("%d\n",ans);55     }56     return 0;57 }