侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 26 条评论

目 录CONTENT

文章目录

【Trie树】最大异或对

GabrielxD
2022-11-10 / 0 评论 / 0 点赞 / 332 阅读 / 986 字
温馨提示:
本文最后更新于 2022-11-11,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

143. 最大异或对


在给定的 NN 个整数 A1A2ANA_1,A_2……A_N 中选出两个进行 xorxor(异或)运算,得到的结果最大是多少?

输入格式

第一行输入一个整数 NN

第二行输入 NN 个整数 A1A_1ANA_N

输出格式

输出一个整数表示答案。

数据范围

1N1051 \le N \le 10^5,
0Ai<2310 \le A_i < 2^{31}

输入样例:

3
1 2 3

输出样例:

3

解题

方法一:Trie 树

思路

把所有数字的二进制表示从高位开始创建为一棵 Trie 树 (每个节点的子节点只有 0 或者 1 两种选择),然后遍历所有数,在 Trie 树中查找尽可能每一位都与当前数字位相反的数(使得异或出来的数尽可能大),构造出异或结果并在遍历过程中维护一个最大的异或结果。

插入操作与普通 Trie 树大同小异,查询操作时,如果能找到与当前数字位相反的位节点就在异或结果中把该位标为 1 否则只能算作两位相同,把异或结果中的该位标为 0,比如:给定数字 2,4,5,12,142, 4, 5, 12, 14,构造出来一棵这样的树:

image-20221110160336281

假如此时遍历到了 5(10)5_{(10)},也就是 0101(2)0101_{(2)},对于每一位在 Trie 树中查找:

image-20221110160909921

找出了 1110(2)1110_{(2)} 可以与 0101(2)0101_{(2)} 做异或取得「 5(10)5_{(10)} 与其他数字做异或可以得到的最大值」: 1011(2)1011_{(2)},注意:从上往下第三层时我们期望找到与 11 相反的位 00,但是树中不存在 00 的分支,所以只能退而求其次走 11 的分支继续向下找了。

看了查找过程后我们就能发现在查找的过程中就可以构造异或结果,也就可以很方便地维护最大异或了。

Trie 树为什么要从高位开始构建而不是低位?
——因为要保证异或出的值尽可能大就应该保证异或出的数高位尽量大,所以在树中搜索的顺序就应该从高位开始,那么构建也应从高位开始。

代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10, M = N * 31;
int sons[M][2], idx;
int n, ans;

void insert(int x) {
    int p = 0;
    for (int i = 30; i >= 0; --i) {
        int curr = x >> i & 1;
        if (sons[p][curr] == 0) sons[p][curr] = ++idx;
        p = sons[p][curr];
    }
}

int query(int x) {
    int p = 0, res = 0;
    for (int i = 30; i >= 0; --i) {
        int curr = x >> i & 1 ^ 1;
        res <<= 1;
        if (sons[p][curr] == 0) p = sons[p][curr ^ 1];
        else {
            p = sons[p][curr];
            ++res;
        }
    }
    return res;
}

int main() {
    scanf("%d", &n);
    while (n--) {
        int x;
        scanf("%d", &x);
        ans = max(ans, query(x));
        insert(x);
    }
    printf("%d\n", ans);
    
    return 0;
}
import java.util.*;	
import java.io.*;

public class Main {
    static final int N = (int) 1e5 + 10, M = N * 31;
    static int[][] sons = new int[M][2];
    static int idx = 0;
    
    static void insert(int x) {
        int p = 0;
        for (int i = 30; i >= 0; --i) {
            int curr = x >> i & 1;
            if (sons[p][curr] == 0) sons[p][curr] = ++idx;
            p = sons[p][curr];
        }
    }
    
    static int query(int x) {
        int p = 0, res = 0;
        for (int i = 30; i >= 0; --i) {
            int curr = x >> i & 1 ^ 1;
            res <<= 1;
            if (sons[p][curr] == 0) p = sons[p][curr ^ 1];
            else {
                p = sons[p][curr];
                ++res;
            }
        }
        return res;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int max = 0;
        while (n-- > 0) {
            in.nextToken();
            int curr = (int) in.nval;
            max = Math.max(max, query(curr));
            insert(curr);
        }
        System.out.println(max);
    }
}

0

评论区