并查集的应用
我居然去查了题解
水平太低了
每次往右边连边，因为只有最后一次染色有用，倒着做就没了
#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;
}
评论 (0)
