题解 Luogu P2391 白雪皑皑

作者: MayFlyyh 分类: 并查集 发布时间: 2018-03-31 01:29 ė 6 没有评论

题解 Luogu P2391 白雪皑皑

题目描述

现在有 N 片雪花排成一列。 Pty 要对雪花进行 M 次染色操作,第 i次染色操作中,把第(ip+q)%N+1 片雪花和第(iq+p)%N+1 片雪花之间的雪花(包括端点)染成颜色 i。其中 p,q 是给定的两个正整数。他想知道最后 N 片雪花被染成了什么颜色。


本题是区间染色问题

显然后面染的颜色会覆盖前面染的颜色

所以我们从后向前处理

那我们如何快速判断哪里染色了,哪里没染色呢?

我们设置f[x]表示染色到x以后,下一次染色在f[x]处

根据定义,初始状态f[x]=x;

对于一个点,我们在第一次染色后就设置f[x]=x+1 (这个点后面的点)

根据定义,我们需要找下一个染色点即为find(x)

重复执行操作,根据并查集路径压缩原理,我们就可以快速求出染x点后应该染的点即为find(x),

当需要染色的点超过了染色区间就退出

思路极其巧妙,感觉像个模型,应该可以运用于更多问题

Code:

#include<bits/stdc++.h>
int f[1000100],col[1000100];
int n,m,p,q;
inline int find(int x){
    if(!f[x]) return x;
    return f[x]=find(f[x]);
}
inline int draw(int x,int y,int i){
    if(x>y) std::swap(x,y);
    int s=find(x),fi=find(y);//,now=s;
    while(s<=y){
        x=find(s);
        if(x>y) return 1;
        col[x]=i,f[x]=x+1;
        s=find(x); //下一个点
    }
}
int main (){
    scanf("%d %d %d %d",&n,&m,&p,&q);
    for(int i=m;i>=1;--i){
        draw((i*p+q)%n+1,(i*q+p)%n+1,i);
    }
    for(int i=1;i<=n;++i)
        printf("%d\n",col[i]);
}

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/192

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部