UOJ#176 新年的繁荣

发布时间:2023年12月21日

UOJ#176 新年的繁荣

UOJ#176 新年的繁荣(VOJ)

题目大意

给你 n n n个在 0 0 0 2 m ? 1 2^m-1 2m?1之间的整数 a 1 , … , a n a_1,\dots,a_n a1?,,an?,令 G G G为一张有 n n n个点的无向完全图,其中第 i i i个点到第 j j j个点的边的边权为 a i and? a j a_i\text{and} \ a_j ai?and?aj?。求 G G G的最大生成树的边权和。

1 ≤ n ≤ 1 0 5 , 0 ≤ m ≤ 18 1\leq n\leq 10^5,0\leq m\leq 18 1n105,0m18


题解

首先,我们可以用 boruvka \text{boruvka} boruvka算法来求最大生成树,具体操作是一开始没有边,我们不断进行以下操作直到整个图只剩一个连通块:

  • 对于当前的图的每个连通块,我们找到连向这个连通块之外的点的边权最小的边,然后将这些边加在图上

因为每次操作之后图上连通块个数至少减少一半,所以总操作次数不会超过 O ( log ? n ) O(\log n) O(logn)次。

那我们怎么找每个连通块连向这个连通块之外的点的边权最小的边呢?我们可以对每个点都求一个连向其所在连通块之外的边权最小的边,用这个边来更新其所在连通块的答案即可。

下面的问题就是对于每个点 i i i,如何求 j j j使得 a i and? a j a_i\text{and} \ a_j ai?and?aj?最大。

我们考虑字典树。一开始把所有 a i a_i ai?都插入到树中。对于每个 a i a_i ai?,我们要在字典树中找到使得 a i and? a j a_i\text{and} \ a_j ai?and?aj?最小的 a j a_j aj?。从大到小枚举 a i a_i ai?的每一位并在字典树中查找:

  • 如果 a i a_i ai?当前位为 1 1 1,则要尽量进入 1 1 1的子树
  • 如果 a i a_i ai?当前位为 0 0 0,则要进入 0 0 0的子树和 1 1 1的子树

我们把 1 1 1的子树复制一份放到 0 0 0的子树上,那当 a i a_i ai?当前位为 0 0 0时,我们就只需要走 0 0 0的子树了。

为了避免选到这个点所在的连通块的 a j a_j aj?,要对字典树上的每个点求其子树中的点所在连通块的编号的最小值和最大值。如果最小值和最大值相等且与当前的 i i i所在的连通块的编号相同,则这棵子树中的 a j a_j aj?不可取;否则,可以进入这棵子树。

因为字典树的深度为 m m m,所以字典树上的节点个数最多为 1 + 2 + ? + 2 m = 2 m + 1 ? 1 1+2+\cdots+2^m=2^{m+1}-1 1+2+?+2m=2m+1?1,那么建树的空间复杂度为 O ( 2 m ) O(2^m) O(2m)。将每个数放入字典树的总时间复杂度为 O ( n m ) O(nm) O(nm)。在合并的时候,最坏的情况下每个点只会被其每个祖先合并一次,所以合并的总时间复杂度为 O ( m 2 m ) O(m2^m) O(m2m)。查询的时间复杂度为 O ( n m ) O(nm) O(nm)

总时间复杂度为 O ( ( 2 m + n ) m log ? n ) O((2^m+n)m\log n) O((2m+n)mlogn),总空间复杂度为 O ( 2 m ) O(2^m) O(2m)

code

#include<bits/stdc++.h>
using namespace std;
const int N=100000;
int n,m,tot=0,a[N+5],fa[N+5];
long long ans=0;
struct trie{
	int mn,mx,a[2];
}w[1<<20];
struct node{
	int x,v;
}mx[N+5];
int find(int ff){
	if(fa[ff]!=ff) fa[ff]=find(fa[ff]);
	return fa[ff];
}
int gtnew(){
	++tot;
	w[tot].a[0]=w[tot].a[1]=w[tot].mx=0;
	w[tot].mn=n;
	return tot;
}
void pt(int s,int id){
	int q,vq=1;
	for(int i=m-1;i>=0;i--){
		q=(s>>i)&1;
		if(!w[vq].a[q]){
			w[vq].a[q]=gtnew();
		}
		vq=w[vq].a[q];
		w[vq].mx=max(w[vq].mx,id);
		w[vq].mn=min(w[vq].mn,id);
	}
}
int merge(int x,int y){
	if(!y) return x;
	if(!x) x=gtnew();
	w[x].mn=min(w[x].mn,w[y].mn);
	w[x].mx=max(w[x].mx,w[y].mx);
	w[x].a[0]=merge(w[x].a[0],w[y].a[0]);
	w[x].a[1]=merge(w[x].a[1],w[y].a[1]);
	return x;
}
void dfs(int u,int dep){
	if(dep<0) return;
	if(w[u].a[0]) dfs(w[u].a[0],dep-1);
	if(w[u].a[1]) dfs(w[u].a[1],dep-1);
	w[u].a[0]=merge(w[u].a[0],w[u].a[1]);
}
node gt(int s,int id){
	int q,vq=1,tmp=0;
	node re;
	trie w0,w1;
	for(int i=m-1;i>=0;i--){
		q=(s>>i)&1;
		w0=w[w[vq].a[0]];
		w1=w[w[vq].a[1]];
		if(q&&(w1.mn!=w1.mx||w1.mn!=id)){
			tmp+=1<<i;
			vq=w[vq].a[1];
		}
		else if(w0.mn!=w0.mx||w0.mn!=id){
			vq=w[vq].a[0];
		}
		else return (node){-1,0};
	}
	re.v=tmp;
	if(w[vq].mn==id) re.x=w[vq].mx;
	else re.x=w[vq].mn;
	return re;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		fa[i]=i;
	}
	int fl=1;
	while(fl){
		fl=0;
		tot=1;
		w[1].a[0]=w[1].a[1]=w[1].mx=0;w[1].mn=n;
		for(int i=1;i<=n;i++) pt(a[i],find(i));
		dfs(1,m-1);
		for(int i=1;i<=n;i++){
			mx[find(i)]=(node){0,-1};
		}
		for(int i=1;i<=n;i++){
			node tmp=gt(a[i],find(i));
			if(tmp.v>mx[find(i)].v) mx[find(i)]=tmp;
		}
		for(int i=1;i<=n;i++){
			if(find(i)==i){
				int v1=i,v2=find(mx[i].x);
				if(v1==v2) continue;
				fl=1;
				fa[v1]=v2;
				ans+=mx[i].v;
			}
		}
	}
	printf("%lld",ans);
	return 0;
}
文章来源:https://blog.csdn.net/tanjunming2020/article/details/135116384
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。