Codeforces

分析

这种奇奇怪怪的生成树题考虑 Boruvka 算法。其核心思想是对每个连通块找到最近的连通块，然后合并。

对于这道题，我们考虑把所有数插入到一棵 Trie 中，那么对于每个节点，其左子树和右子树中必定只由一条边相连。这是因为在执行 Boruvka 算法的过程中，必定是左右子树先分别连通，然后再通过一条边合并在一起。

那么我们只需要知道两个数组间两两异或的最小值，将一个数组中所有数插入到一棵 Trie 中，然后把另一个数组中的所有数丢上去求一个最小异或和即可。

复杂度可以这样考虑：Trie 树共有 $\log W$ 层，每层都需要 $\mathcal{O}(n \log W)$ 的时间复杂度来处理，因此总时间复杂度 $\mathcal{O}(n\log^2 W)$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 200000 + 10;

int n, a[N];
vector<int> vec;

int ch[N * 40][2], tot = 0;
void init() {
    for (int i = 0; i <= tot; ++i) ch[i][0] = ch[i][1] = 0;
    tot = 0;
}
void insert(int w) {
    int u = 0;
    for (int i = 29; ~i; --i) {
        int c = (w >> i) & 1;
        if (!ch[u][c]) ch[u][c] = ++tot;
        u = ch[u][c];
    }
}
int query(int w) {
    int u = 0, res = 0;
    for (int i = 29; ~i; --i) {
        int c = (w >> i) & 1;
        if (ch[u][c]) u = ch[u][c];
        else res |= 1 << i, u = ch[u][c ^ 1];
    }
    return res;
}

ll solve(vector<int> &v, int k) {
    if (v.empty() || k < 0) return 0;
    vector<int> v0, v1;
    for (int i : v) {
        if (i & (1 << k)) v1.emplace_back(i);
        else v0.emplace_back(i);
    }
    int mn = 0;
    if (!v0.empty() && !v1.empty()) {
        mn = INT_MAX, init();
        for (int i : v0) insert(i);
        for (int i : v1) mn = min(mn, query(i));
    }
    return mn + solve(v0, k - 1) + solve(v1, k - 1);
}

int main() {
    n = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    for (int i = 1; i <= n; ++i) vec.emplace_back(a[i]);
    printf("%lld\n", solve(vec, 29));
    return 0;
}