题解 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]);
}