BZOJ5362: [Lydsy1805月赛]quailty 算法

https://lydsy.com/JudgeOnline/problem.php?id=5362

分析:

题意即求一个最小基环树森林，两点之间边权为异或值。
这题的思路很好，先排序，我们二进制分组，将\(0\)和\(1\)分成两部分，显然这两部分之间的边能不连就不连。
但也有必须连的情况，就是出现某个集合大小小于等于\(2\)的情况，内部无法自身构成基环树，需要和另外一个集合连边，此时我们暴力找最小的边即可。
时间复杂度为\(O(nlogn)\)。

代码:

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

#define N 300050

typedef long long ll;

int n,a[N],k=30;

ll ans;

void solve(int l,int r,int d) {

	if(d==-1||l>=r) return ;

	if(l==r-1) {ans+=a[l]^a[r]; return ;}

	int mid=l,i,j;

	for(;mid<=r&&!((a[mid]>>d)&1);mid++) ;

	solve(l,mid-1,d-1);

	solve(mid,r,d-1);

	int ls=mid-l,rs=r-mid+1;

	if(ls>2&&rs>2) return ;

	if(ls<1||rs<1) return ;

	int mn1=1<<30,mn2=1<<30;

	for(i=l;i<mid;i++) {

		for(j=mid;j<=r;j++) {

			int x=a[i]^a[j];

			if(x<mn1) mn2=mn1,mn1=x;

			else if(x<mn2) mn2=x;

		}

	}

	if(ls<=2&&rs<=2) ans+=mn1+mn2;

	else ans+=mn1;

}

int main() {

	int T;

	scanf("%d",&T);

	while(T--) {

		scanf("%d",&n);

		int i;

		for(i=1;i<=n;i++) scanf("%d",&a[i]);

		sort(a+1,a+n+1);

		ans=0;

		solve(1,n,k);

		printf("%lld\n",ans);

	}

}

巴特西

BZOJ5362: [Lydsy1805月赛]quailty 算法

BZOJ5362: [Lydsy1805月赛]quailty 算法

最新文章

热门文章