【BZOJ2054】疯狂的馒头（并查集，线段树）

时间：2023-03-09 05:20:10
【BZOJ2054】疯狂的馒头（并查集，线段树）

【BZOJ2054】疯狂的馒头（并查集，线段树）

题面

BZOJ

然而权限题，随便找个离线题库看看题吧。

题解

线段树就是个暴力，如果数据可以构造就能卡掉，然而不能构造，要不然复杂度瓶颈成为了读入了。既然这样，线段树随便跑跑就过了。

大概的做法就是，后面的颜色只要染上了显然就和前面的颜色无关了，所以用从后往前枚举颜色染就好了。

#include<iostream>

#include<cstdio>

using namespace std;

#define MAX 1000100

#define lson (now<<1)

#define rson (now<<1|1)

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

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

	return t?-x:x;

}

int n,m,p,q;

int t[MAX<<2];

void Modify(int now,int l,int r,int L,int R,int w)

{

	if(t[now])return;

	if(l==r){t[now]=w;return;}

	int mid=(l+r)>>1;

	if(L<=mid)Modify(lson,l,mid,L,R,w);

	if(R>mid)Modify(rson,mid+1,r,L,R,w);

	t[now]=t[lson]&&t[rson];

}

void Output(int now,int l,int r)

{

	if(l==r){printf("%d\n",t[now]);return;}

	int mid=(l+r)>>1;

	Output(lson,l,mid);Output(rson,mid+1,r);

}

int main()

{

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

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

	{

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

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

		Modify(1,1,n,l,r,i);

	}

	Output(1,1,n);

	return 0;

}

正常点的方法：和线段树的考虑方法类似，倒着染色。然后每次暴力\(for\)区间，并查集加速找下个未被染色的位置。

#include<iostream>

#include<cstdio>

using namespace std;

#define MAX 1000100

int n,m,p,q,f[MAX],col[MAX];

int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}

int main()

{

	cin>>n>>m>>p>>q;for(int i=1;i<=n+1;++i)f[i]=i;

	while(m)

	{

		int l=(1ll*m*p+q)%n+1,r=(1ll*m*q+p)%n+1;if(l>r)swap(l,r);

		for(int i=getf(l);i<=r;i=getf(i+1))col[i]=m,f[i]=getf(i+1);--m;

	}

	for(int i=1;i<=n;++i)printf("%d\n",col[i]);

	return 0;

}

相关文章