Mayflyyh
Mayflyyh
MayFlyyh's Blog
题解 Luogu P2391 白雪皑皑

题解 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]);
}
本文链接:http://www.mayflyyh.com/archives/192
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      并查集      题解 Luogu P2391 白雪皑皑
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

MayFlyyh's Blog

题解 Luogu P2391 白雪皑皑
题解 Luogu P2391 白雪皑皑 题目描述 现在有 N 片雪花排成一列。 Pty 要对雪花进行 M 次染色操作,第 i次染色操作中,把第(ip+q)%N+1 片雪花和第(iq+p)%N+1 片雪花之间的雪…
扫描二维码继续阅读
2018-03-31