BZOJ2054：疯狂的馒头

浅谈并查集：https://www.cnblogs.com/AKMer/p/10360090.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=2054

倒着枚举颜色覆盖，每次暴力枚举区间内还没有颜色的格子涂色，然后用并查集合并已经涂了色的格子。

时间复杂度：\(O(\alpha{n})\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=1e6+5;

int n,m,p,q;

int fa[maxn],ans[maxn];

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

int find(int x) {

	if(fa[x]==x)return x;

	return fa[x]=find(fa[x]);

}

int main() {

	n=read(),m=read(),p=read(),q=read();

	for(int i=1;i<=n+1;i++)fa[i]=i;

	for(int i=m;i;i--) {

		int l=(1ll*i*p+q)%n+1,r=(1ll*i*q+p)%n+1;

		if(r<l)swap(l,r);

		for(int pos=find(l);pos<=r;pos=fa[pos+1])

			ans[pos]=i,fa[pos]=find(pos+1);

	}

	for(int i=1;i<=n;i++)

		printf("%d\n",ans[i]);

	return 0;

}

巴特西

BZOJ2054：疯狂的馒头

最新文章

热门文章