首页 > 其他分享 >题解:CF888G Xor-MST

题解:CF888G Xor-MST

时间:2024-09-23 22:03:34浏览次数:8  
标签:ch Xor int 题解 MST merge tail siz uu

题解:CF888G Xor-MST

题目大意:给定 \(n\) 个点的点权, 任意两点间边权是点权的异或和。求这张完全图的 MST 的权值。

思路:

Boruvka + Trie树 + 按位贪心。

关键就在于如何求出 Boruvka 中的 best 数组。

考虑对点权建 trie 树,对于节点 \(i\) 本轮的连边,就是找 “和它最相似” 的那个。

我最初的想法是只建一棵 trie 树,那么上述过程只需要每次 尽量 按照 \(a[i]\) 来走就行,但接着就发现不太对,因为求不出 "除去 \(i\) 所在集合中的点权 的影响后的最好方案"。

参考了这篇博客 ,发现给 全局 和 每个集合 分别建树是个很妙的想法,这样就可以轻松减去本集合的权值。具体实现是记录一个 siz 数组。

建树,统计答案都已经实现了,最后合并一下两棵树的信息就行。

感觉难点就在于理清楚思路。比较难写的是merge和query,细节比较多。

时间复杂度 \(O(30nlogn)\)

#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=r;++i)
#define G(i,r,l) for(int i(r);i>=l;--i)
#define pii pair<int, int>
#define fi first
#define se second
using ll = long long;
using namespace std;
const int N = 2e5 +5;
const ll inf = 0x3f3f3f3f;
int a[N], fa[N], best[N], ch[50 * N][2], val[N], root[N], siz[50 * N], tail[50 * N];
int n, num = 0;
inline int get(int x){
	return (fa[x]==x) ? x : fa[x] = get(fa[x]);
}
void insert(int &uu, int idx, int w){
	if(!uu) uu = ++num;
	int u = uu;
	G(i, 30, 0){
		int o = w >> i & 1;
	 	siz[u] ++ ;
		if(!ch[u][o]) ch[u][o] = ++num;
	 	u = ch[u][o];
	}
	tail[u] = idx; siz[u] = 1;
}
void merge(int &p, int q){
	if(!p || !q) return (void)(p = p + q);
	merge(ch[p][0], ch[q][0]);
	merge(ch[p][1], ch[q][1]);
	siz[p] = siz[ch[p][0]] + siz[ch[p][1]];// 合并的一部分, 合并后q就不会再使用了, 所以只操作p就可以了 
	tail[p] = tail[q];//可以去掉这个赋值? 对于非叶子结点, tail都是0, 但对于叶子结点不清楚 >>>>>>>>>>>>>>>>>>>>>>>>>>
}
pii query(int u, int v, int w){
	int ans = 0;
	G(i, 30, 0){
		int c = (w >> i) & 1;
		if(ch[u][c] && siz[ch[u][c]] - siz[ch[v][c]] > 0) u = ch[u][c], v = ch[v][c];
		else ans |= (1 << i), u = ch[u][c ^ 1], v = ch[v][c ^ 1];//v 的 移动本质上是 u 的同步, 所以都要 c ^ 1 
	}
	return make_pair(tail[u], ans);//最后选中了哪个点, 代价是多少 
}
ll boruvka(){
	F(i, 1, n) fa[i] = i;
	int pd = 1;
	ll sum = 0;
	while(pd){
		pd = 0;
		F(i, 1, n) val[i] = inf, best[i] = 0;
		F(i, 1, n){
			int x = get(i);
			pii ret = query(root[0], root[x], a[i]);//找和a[i]异或得到的结果最小的点 
			int y = get(ret.fi), w = ret.se;
			//注意y要找祖先!
			if(x != y){//不在同一集合才能连 
				if(w < val[x]) best[x] = y, val[x] = w;
				if(w < val[y]) best[y] = x, val[y] = w;
			}
		}
		F(i, 1, n){
			if(val[i] < inf && get(i) != get(best[i])){
				//不用判 best[i]!=0, 因为如果=0, 那val[i]必然=inf, 这也是为什么best可以不清空的原因
				sum += val[i];
				pd = 1;
				merge(root[get(i)], root[get(best[i])]);
				fa[get(best[i])] = get(i);	
			}
		}
	}
	return sum;
}
signed main(){
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n; F(i, 1, n) cin >> a[i];
	sort(a + 1, a + 1 + n);
	n = unique(a + 1, a + 1 + n) - a - 1;//要去重, 相同权值的点连边其实可以全部等效在一个点上, 而且不去重算出来的siz会加倍, 问题就多了 
	F(i, 1, n)insert(root[0], i, a[i]), insert(root[i], i, a[i]);
	cout << boruvka() << '\n';
	return 0;
}

标签:ch,Xor,int,题解,MST,merge,tail,siz,uu
From: https://www.cnblogs.com/superl61/p/18427983

相关文章

  • SP1825 FTOUR2 - Free tour II 题解
    题目传送门前置知识点分治|树状数组解法维护点对信息,考虑点分治。本题比luoguP4149[IOI2011]Race多了个前缀查询\(\max\)。套个支持单点修改、区间查询\(\max\)的数据结构即可。直接线段树维护区间\(\max\)貌似会TLE,换成树状数组维护前缀\(\max\)即可。注......
  • LGP3183 题解
    原题链接:P3183[HAOI2016]食物链。难度:Easy。根据定义,食物链是一个DAG,所以可以进行拓扑排序。食物链也就转化成了:图中从一个入度为\(0\)的点到一个出度为\(0\)的点的路径。那么只需要拓扑排序求出所有起点到每个点的路径条数,然后累加出度为\(0\)的点的值即可。需要注......
  • LGP1901 题解
    原题链接:P1901发射站难度:Easy。注意到"最近的且比它高",容易想到用单调栈维护每个能量发射站左右第一个比它高的,最后统计答案即可。具体的令f[i][0/1]表示能量发射站\(i\)右边/左边第一个\(h_x>h_i\)的位置\(x\)。用单调栈从左向右扫一遍,得到f[i][0]。用单调栈从右......
  • [题解] ICPC网络预选赛 2024 第二场 E Escape (含题目翻译)
    [题解]ICPC网络预选赛2024第二场EEscape(含题目翻译)tag:图论、BFS、最短路题干为原文DeepL翻译题目描述Sneaker在一个巨大的迷宫中醒来,现在他想逃离这个迷宫。通过迷宫中每个房间的地图,Sneaker了解了迷宫的结构。迷宫由......
  • 【题解】Solution Set - NOIP2024集训Day36 dp 优化 + 状态设计
    【题解】SolutionSet-NOIP2024集训Day36dp优化+状态设计https://www.becoder.com.cn/contest/5550最后一题较难。「NOIP2023」天天爱打卡考虑dp。\(f_{i,j}\):前\(i\)天,到第\(i\)天为止连续打卡\(j\)天。有转移:\[f_{i,0}=\max(f_{i,j})\\f_{i,j}=\max(f_{i......
  • Codeforces Round 972(Div.2)题解
    CodeforcesRound972(Div.2)题解A.SimplePalindrome贪心贪心,尽可能元素数量平均,并且相同字母放在一起。#include<bits/stdc++.h>usingnamespacestd;#definefffirst#definesssecond#definepbpush_back#defineall(u)u.begin(),u.end()#defineendl'\n'#de......
  • Codeforces Round 973 (Div.2) A-E题解
    CodeforcesRound973(Div.2)A-E题解比赛传送门A.Zhan'sBlender数学显然答案为\(\lceil\frac{n}{min(x,y)}\rceil\)。#include<bits/stdc++.h>usingnamespacestd;#definefffirst#definesssecond#definepbpush_back#defineall(u)u.begin(),u.en......
  • 题解:AT_abc372_e [ABC372E] K-th Largest Connected Components
    题意给出\(q\)个操作。将\(u\)和\(v\)连边。问\(u\)所在的连通块中编号第\(k\)大的点。思路连通块很容易想到并查集,求第\(k\)大可以用平衡树(虽然赛时没看到\(k\le10\)),合并时将信息从将小的连通块合并到大的连通块,这样可以减少时间复杂度。什么?你不会写平衡......
  • 题解:AT_arc184_a [ARC184A] Appraiser
    题意\(1000\)个硬币中有\(10\)个假币,你每次可以询问两个位置的硬币类型是否相同,你需要用不超过\(950\)次询问找出所有假币的位置。思路将前\(990\)个硬币每\(11\)个分一组,共\(90\)组,余\(10\)个单独分一组。询问每组第\(1\)个硬币和这组后面硬币的关系。因为只......
  • CF1270H Number of Components 题解
    Description给一个长度为\(n\)的数组\(a\),\(a\)中的元素两两不同。对于每个数对\((i,j)(i<j)\),若\(a_i<a_j\),则让\(i\)向\(j\)连一条边。求图中连通块个数。支持\(q\)次修改数组某个位置的值,每次修改后输出图中连通块个数。\(n,q\le5\times10^5,1\lea_i\le10^......