Acwing.143 最大异或对(trie树)

题目

在给定的N个整数A1，A2 . …Ax中选出两个进行xor(异或)运算，得到的结果最大是多少?
输入格式
第一行输入一个整数N。
第二行输入N个整数A1~AN。

输出格式

输出一个整数表示答案。

数据范围

1 ≤N ≤105,0≤A<231

• 输入样例:

3
1 2 3
1
2

• 输出样例

3
1

题解

import java.util.Scanner;

/**
 * @author akuya
 * @create 2023-07-24-0:00
 */
public class Mxor {
    static int N=100010;
    static int M=31*N;

    static int n;
    static int a[]=new int[N];
    static int son[][]=new int[M][2];
    static int idx;

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        int res=0;
        for(int i=0;i<n;i++){
            a[i]=scanner.nextInt();
        }


        for(int i=0;i<n;i++){
            insert(a[i]);
            int t=query(a[i]);
            res=Math.max(res,a[i]^t);
        }

        System.out.println(res);
    }

    public static void insert(int x){

        int p=0;
        for(int i=30;i>=0;i--){
            int u=x>>i&1;
            if(son[p][u]==0) son[p][u]=++idx;
            p=son[p][u];
        }

    }

    public static int query(int x){
        int p=0;
        int res=0;
        for(int i=30;i>=0;i--){
            int u=x>>i&1;
            if(son[p][u^1]!=0){
                p=son[p][1^u];
                res=res*2+1^u;
            }else{
                p=son[p][u];
                res=res*2+u;
            }
        }


        return res;
    }
}

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

思路

正常遍历时间复杂度为n²，利用trie树存起来，然后分解成二进制遍历。可以压缩时间复杂度到O（n）*O(31)。这样就不会超时了