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

    CodeForces - 888G Xor-MST

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

    本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
    说我们IIS7站长博客,有一篇博文用了他们的图片。
    要求我们给他们一张图片6000元。要不然法院告我们

    为避免不必要的麻烦,IIS7站长博客,全站内容图片下架、并积极应诉
    博文内容全部不再显示,请需要相关资讯的站长朋友到必应搜索。谢谢!

    另祝:版权碰瓷诈骗团伙,早日弃暗投明。

    相关新闻:借版权之名、行诈骗之实,周某因犯诈骗罪被判处有期徒刑十一年六个月

    叹!百花齐放的时代,渐行渐远!



    题面

    自己去看

    题解

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

    对于权值一样的直接合并, 且开销为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;
    }