题解：P7384 「EZEC-6」分组

提供一种

O(n+\log v \alpha(\log v))

的做法。

80 分做法同官解的 80 分。

考虑如何优化，发现可以在一定有两个集合合并时再拆位合并。于是记录每一位所在集合的并，需要时（当前处理的数有一位为 1 且这位不在集合并中）再合并。每次

O(\log v\alpha(\log v))

合并一次，再

O(\log v)

求集合的并即可做到

O(n+\log v \alpha(\log v))

。

代码。

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e7+100;
int n;
int a[N],f[N],vv[N],g[N];
bool v[N];
inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
inline void read(T& r) {
	r=0;bool w=0; char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9') r=r*10+(ch^48), ch=getchar();
	r=w?-r:r;
}
signed main()
{
	read(n);
	int x,y,z=0,ans=0;
	for(int i=1;i<=n;i++)read(a[i]),g[i]=i;
	for(int i=0;i<63;i++)f[i]=i;
	for(int i=1;i<=n;i++)
	{
		z|=a[i];
		if(!a[i]){ans++;continue;}
		if((vv[__builtin_ctzll(a[i]&-a[i])]&a[i])>=a[i])continue;
		x=find(__builtin_ctzll(a[i]&-a[i])),y=0;
		for(int j=0;j<63;j++)
		{
			if(a[i]&(1ll<<j))f[find(j)]=x;
			if(find(j)==x)y|=1ll<<j;
		}
		x=find(x);
		for(int j=0;j<63;j++)if(find(j)==x)vv[j]=y;
	}
	for(int i=0;i<63;i++)
	{
		if(!(z&(1ll<<i)))continue;
		if(!v[find(i)])v[find(i)]=1,ans++;
	}
	cout<<ans;
}

题解：P7384 「EZEC-6」分组

文章操作

相关推荐

评论

题解：P7384 「EZEC-6」分组