当前位置 博文首页 > 文章内容

    CodeForces - 888G Xor-MST

    作者:洛绫璃 栏目:未分类 时间:2020-10-17 18:00:30

    题面

    自己去看

    题解

    最小生成树, 无非是并查集, 合并就完事

    对于权值一样的直接合并, 且开销为0,

    相当于原数组去重,

    当然是从最高位考虑, 最高位相同的先合并, 在和最高位不同的合并

    像不像分治?

    trie 字典树, 从最高位不断深入, 在不断合并

    #include <bits/stdc++.h>
    #define all(n) (n).begin(), (n).end()
    #define se second
    #define fi first
    #define pb push_back
    #define mp make_pair
    #define sqr(n) (n)*(n)
    #define rep(i,a,b) for(int i=(a);i<=(b);++i)
    #define per(i,a,b) for(int i=(a);i>=(b);--i)
    #define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
    using namespace std;
    typedef unsigned long long ull;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int, int> PII;
    typedef pair<ll, ll> PLL;
    typedef vector<int> VI;
    
    template<class T1, class T2> bool umin(T1& a, T2 b) { return a > b ? (a = b, true) : false; }
    template<class T1, class T2> bool umax(T1& a, T2 b) { return a < b ? (a = b, true) : false; }
    template<class T> void clear(T& a) { T().swap(a); }
    
    const int N = 2e5 + 5, inf = 1 << 30;
    
    int n, m, _, k;
    
    struct Trie {
        int trie[N * 29][2], a[N * 29], tot = 1, ended[N * 29];
        VI c[N * 39];
    
        void insert(int s) {
            int p = 1;
            per(i, 29, 0) {
                int ch = s >> i & 1;
                if (!trie[p][ch]) trie[p][ch] = ++tot;
                c[p].pb(s); a[p] = i;
                p = trie[p][ch];
                if (ch) s -= 1 << i;
            }
            ended[p] = true;
        }
    
        int search(int s, int p) {
            int ans = 0;
            per(i, a[p], 0) {
                int ch = s >> i & 1;
                if (trie[p][ch]) p = trie[p][ch];
                else p = trie[p][ch ^ 1], ans += 1 << i;
            }
            return ans;
        }
    } tr;
    
    ll ans = 0;
    
    void dfs(int p) {
        if (tr.c[p].size() == 1) return;
        rep(i, 0, 1) if (tr.trie[p][i]) dfs(tr.trie[p][i]);
        if (!tr.trie[p][0] || !tr.trie[p][1]) return;
    
        int l = tr.trie[p][0], r = tr.trie[p][1];
        if (tr.c[l].size() > tr.c[r].size()) swap(l, r);
        ll cur = inf;
        for (auto& i : tr.c[l]) umin(cur, tr.search(i, r));
        if (cur != inf) ans += cur;
        ans += 1 << tr.a[p];
    }
    
    int main() {
        IOS; cin >> n;
        VI a(n);
        for (auto& i : a) cin >> i;
        sort(all(a)); a.erase(unique(all(a)), a.end());
        for (auto& i : a) 
            tr.insert(i);
        dfs(1); cout << ans;
        return 0;
    }