题解 P2391 【白雪皑皑】

· · 题解

并查集维护序列连通性的一道好题。

我们知道，并查集可以维护图的连通性，当然类比到序列上也是可行的。

在图上，fa[x]=fa[y]，则称x,y连通。

而在这道题中，可以用fa[x]表示x后第一个可操作的节点。

考虑题目含义，一个雪花的颜色是它最后被染上的颜色。

我们可以倒序枚举染色操作，在染色区间内进行跳跃染色，并维护连通性。

类似题目

这道题目暴力可过，但是如果是上面推的那道题，一个点可以多次操作，暴力大概率过不了。

//fa[i]表示，i前面第一个没染色的雪花
#include<bits/stdc++.h>
using namespace std;
#define reg register
inline int read(){
    reg char c;reg int f=1,x=0;
    while(!isdigit(c)) { if(c=='-') f=-1;c=getchar(); }
    while(isdigit(c)) { x=x*10+c-'0';c=getchar(); }
    return x*f;
}
int n,m,p,q,fa[1000001],col[1000001];
inline int myfind(int x){ if(x==fa[x]) return x;return fa[x]=myfind(fa[x]); }
int main(){
    n=read(),m=read(),p=read(),q=read();
    for(reg int i=1;i<=n;++i) fa[i]=i;
    for(reg int i=m;i>=1;--i){//依照题意，倒序染色（颜色以最后一次染上的颜色为准）
        int l=(i*p+q)%n+1,r=(i*q+p)%n+1;
        if(l>r) swap(l,r);
        for(reg int j=r;j>=l;){
            int t=myfind(j);
            if(t==j){
                col[j]=i,fa[j]=myfind(j-1)/*维护连通性*/;
            }j=fa[j];//直接跳到下一个可染色的点
        }
    }
    for(reg int i=1;i<=n;++i) printf("%d\n",col[i]);
}

再推荐一道题，需要与贪心结合。

supermarket