5
18
2016
0

[BZOJ2054] 疯狂的馒头

并查集的应用

我居然去查了题解

水平太低了

每次往右边连边,因为只有最后一次染色有用,倒着做就没了

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int N=1000005;

int n,m,p,q,f[N],a[N];

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

int main(){
freopen("2054.in","r",stdin);
freopen("2054.out","w",stdout);
scanf("%d %d %d %d",&n,&m,&p,&q);
for(int i=m;i;i--){
	int l=(i*p+q)%n+1,r=(i*q+p)%n+1;
    if(l>r)swap(l,r);
    for(int j=Find(l);j<=r;j=Find(j)){
		if(!a[j])a[j]=i;
		f[j]=j+1;
    }
}
for(int i=1;i<=n;i++)printf("%d\n",a[i]);
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 433

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com