CF888G 【Xor-MST】

妙妙题……

看到\(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;

}

巴特西

CF888G 【Xor-MST】

\(Code:\)

最新文章

热门文章