The XOR Largest Pair

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 1341 字

01 Trie 贪心走反相位求最大异或

一本通
例

正文

// 原题：https://oj.yecheng.tv/p/T1472
// 题意：给定 N 个小于 2^31 的非负整数，从中选两个数求异或，输出能得到的最大值。
// 思路：把每个数按二进制从高位到低位建成 01 Trie。查询时每一步优先走向与当前位相反的分支，能让该位异或结果为 1，贪心从高位往下走即得最大异或值。
// 复杂度：O(N × 31) 时间 / O(N × 31) 空间
// 易错点：最高位要从 30 开始（A_i < 2^31），从更低位开始会漏掉最高位的贡献。
// 易错点：要保证 Trie 非空才有分支可走，第一个数必须先插入再查询，否则查询时树是空的。
#include <bits/stdc++.h>
using namespace std;
struct Node {
    int ch[2];
    Node(){
        ch[0] = ch[1] = 0;
    }
};
vector<Node> tr;
void insertVal(int x){
    int u = 0;
    for(int i = 30; i >= 0; i--){
        int b = (x >> i) & 1;
        if(!tr[u].ch[b]){
            tr[u].ch[b] = (int)tr.size();
            tr.push_back(Node());
        }
        u = tr[u].ch[b];
    }
}
int queryVal(int x){
    int u = 0;
    int res = 0;
    for(int i = 30; i >= 0; i--){
        int b = (x >> i) & 1;
        if(tr[u].ch[b ^ 1]){
            res |= (1 << i);
            u = tr[u].ch[b ^ 1];
        }else{
            u = tr[u].ch[b];
        }
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if(!(cin >> n)) return 0;
    tr.reserve((n + 1) * 31);
    tr.push_back(Node());
    int ans = 0;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        insertVal(x);
        int v = queryVal(x);
        if(v > ans) ans = v;
    }
    cout << ans << "\n";
    return 0;
}

The XOR Largest Pair

正文

一本通·提高篇的其它内容