题解 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]);
}
0 条评论