【LOJ10050】The XOR Largest Pair（字典树）

problem

• 给定n个整数，在其中任意选出两个进行xor运算，得到的结果最大值是多少？
• n<1e5，ai在int范围内

solution

• 朴素枚举，O(n^2), TLE
• 考虑异或运算，相同为0，相反为1。我们希望最终值尽可能大，即1尽可能多。
• 将每个整数看做二进制串，建立字典树。
• 接下来遍历ai，并查找字典树。查找中的策略是每次选择与ai当前位相反的字符指针向下访问，即可得到最大值。
• 复杂度O(31*n)

codes

#include<iostream>
using namespace std;
const int maxn = 1e5+10;

int tot, tire[maxn*32][2];
void insert(int x){
    int u = 0;
    for(int i = 31; i >= 0; i--){
        int c = (x>>i)&1;
        if(!tire[u][c])tire[u][c] = ++tot;
        u = tire[u][c];
    }
}
int query(int x){
    int u = 0, ans = 0;
    for(int i = 31; i >= 0; i--){
        int c = (x>>i)&1;
        if(tire[u][!c])u = tire[u][!c], ans = (ans<<1)|1;
        else u = tire[u][c], ans = ans<<1;
    }
    return ans;
}

int a[maxn];
int main(){
    ios::sync_with_stdio(false);
    int n;  cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>a[i];  insert(a[i]);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
        ans = max(ans, query(a[i]));
    cout<<ans<<'\n';
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/81559800