(CH1602)最大异或和

January 25, 2020 · 算法 · 1085次阅读
#include <iostream>
//树上贪心算法,虽然题目说的是两两xor,但其实只要想办法每次都走反向的数字就能找到最优解
using namespace std;
const int maxn = 1e5 + 1;
const int SIZE = maxn * 32;
int tot = 1;//定义节点编号,初始化为1
int a[maxn], n;//存储所有数据
struct trieNode {
    int foot[2];//定义每个节点上的数字是0还是1
} trie[SIZE];

void insert(int num) {
    int p = 1, ch;
    for (int i = 31; i >= 0; i--) {
        ch = num >> i & 1;
        if (!trie[p].foot[ch]) trie[p].foot[ch] = ++tot;
        p = trie[p].foot[ch];
    }
}

int query(int num) {
    int p = 1, ans = 0, ch;
    for (int i = 31; i >= 0; i--) {
        ch = num >> i & 1;
        if (trie[p].foot[ch ^ 1]) {//这里异或操作就是0变1,1变0
            ans |= 1 << i;//神奇操作,等同于二进制转换十进制操作(会自动相加的)
            p = trie[p].foot[ch ^ 1];//继续顺着当前的路走
        } else p = trie[p].foot[ch];//如果没有相反的路可以走,就按照唯一的路走
    }
    return ans;
}

int getAns() {
    int ans = 0;
    for (int i = 0; i < n; i++) ans = max(ans, query(a[i]));
    return ans;
}

int main() {
    int ans = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        insert(a[i]);//创建trie树
    }
    ans = getAns();
    cout << ans;
    return 0;
}

Trie贪心字典树

最后编辑于4年前

添加新评论