Xor-MST

思路

异或最小生成树，这里采用了一种分治的方法来贪心求解最值：

• 首先我们对所有的点权值从小到大排个序，从高位开始在中间找到一个这个位置上的分界点分成两个集合，然后再通过递归的去求解两个集合。
• 在递归的时候，对两个分开的集合，我们通过树去贪心的在两个集合连上一条边，把这条边加入我们的答案。

为什么这样是对的：显然我们分成两个集合我们可以抵消掉高位的一大堆一样的东西，这个时候，我们可以保证我们的贪心策略是正确的。

为什么我们要合并两个集合：假设左边集合有个点，右边集合有个点，显然左边最多链接条边，右边最多链接条边，要使这个点形成一颗树，必然我们要从左边选择一个点，右边一个点链接一条边，这个时候选点连边我们就可以贪心求解了。

代码

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 10;

int trie[N * 31][2], a[N], n, tot;

void insert(int x) {
    int rt = 0;
    for(int i = 30; i >= 0; i--) {
        int now = (x >> i) & 1;
        if(!trie[rt][now]) {
            trie[rt][now] = ++tot;
            rt = trie[rt][now];
            trie[rt][0] = trie[rt][1] = 0;
        }
        else {
            rt = trie[rt][now];
        }
    }
}

int find(int x) {
    int ans = 0, rt = 0;
    for(int i = 30; i >= 0; i--) {
        int now = (x >> i) & 1;
        if(trie[rt][now]) {
            rt = trie[rt][now];
        }
        else {
            rt = trie[rt][now ^ 1];
            ans |= 1 << i;
        }
    }
    return ans;
}

ll ans = 0;

void dfs1(int l, int r, int dep) {
    if(dep < 0 || l >= r) return ;
    int mid = l - 1;
    while(mid < r && ((a[mid + 1] >> dep) & 1) == 0) mid++;
    dfs1(l, mid, dep - 1);
    dfs1(mid + 1, r, dep - 1);
    if(mid == l - 1 || mid == r) return ;
    tot = 0;
    trie[tot][0] = trie[tot][1] = 0;
    for(int i = l; i <= mid; i++) {
        insert(a[i]);
    }
    int temp = INT_MAX;
    for(int i = mid + 1; i <= r; i++) {
        temp = min(temp, find(a[i]));
    }
    ans += temp;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a + 1, a + 1 + n);
    dfs1(1, n, 29);
    printf("%lld\n", ans);
    return 0;
}