Nemlit 的博客

Nemlit 的博客

By a konjac

题解 CF888G 【Xor-MST】

posted on 2019-10-14 23:25:38 | under 题解 |

妙妙题……

~~看到 $MST$ ,想到 $Kruskal$ ,看到异或,想到 $Trie$ ~~

首先我们模拟一下 $Kruskal$ 的流程:找到最小边,如果联通就忽略,未联通就加边

我们把所有点权值加入 $0-1\ Trie$ 中,然后画张图,可以发现有 $n-1$ 个点是有两个儿子的,而其他点都是只有 $0/1$ 个儿子

权值最小的边应该是 $Trie$ 中, $LCA$ 深度最大的两个数

而且这 $n-1$ 个节点是一些在 $Trie$ 中结尾节点的 $LCA$

所以我们只需要遍历整颗 $Trie$ ,然后对所有可能为 $LCA$ 的点,找到一条最小的边,把它的两颗子树合并起来即可

一个小 $trick:$ 我们可以把所有元素排好序,因为 $Trie$ 上的点从左往右看是递增的,于是 $Trie$ 的每一个节点就会对应排好序的数列中的一段区间,这样就不需要启发式合并之类的复杂操作了

$Code:$

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf (1 << 30)
#define rep(i, s, t) for(int i = s; i <= t; ++ i)
#define maxn 200005
int n, m, a[maxn], L[maxn * 32], R[maxn * 32], ch[2][maxn * 32], rt, cnt;
void insert(int&k, int id, int dep) {
    if(!k) k = ++ cnt;
    if(!L[k]) L[k] = id; R[k] = id;
    if(dep == -1) return;
    insert(ch[(a[id] >> dep) & 1][k], id, dep - 1);
}
int query(int k, int x, int dep) {
    if(dep == -1) return 0;
    int v = (x >> dep) & 1;
    if(ch[v][k]) return query(ch[v][k], x, dep - 1);
    return query(ch[v ^ 1][k], x, dep - 1) + (1 << dep);
}
int dfs(int k, int dep) {
    if(dep == -1) return 0;
    if(ch[0][k] && ch[1][k]) {
        int ans = inf;
        rep(i, L[ch[0][k]], R[ch[0][k]]) {
            ans = min(ans, query(ch[1][k], a[i], dep - 1) + (1 << dep));
        }
        return dfs(ch[0][k], dep - 1) + dfs(ch[1][k], dep - 1) + ans;
    }
    else if(ch[0][k]) return dfs(ch[0][k], dep - 1);
    else if(ch[1][k]) return dfs(ch[1][k], dep - 1);
    return 0;
}
signed main() {
    scanf("%lld", &n);
    rep(i, 1, n) scanf("%lld", &a[i]);
    sort(a + 1, a + n + 1);
    rep(i, 1, n) insert(rt, i, 30);
    printf("%lld", dfs(rt, 30));
    return 0;
}