2054: 疯狂的馒头Time Limit:10 SecMemory Limit:162 MBSubmit:449Solved:175[Submit][Status]Description
Input
第一行四个正整数N，M，p，q
Output
一共输出N行，，第i行表示第i个馒头的最终颜色（如果最终颜色是白色就输出0）。
Sample Input
4 3 2 4
Sample Output
2230
HINT
并查集。
（一看这道题认为是简单的线段数打标记，但是数据范围显然不可以）
每个馒头的颜色取决于最后染他的是什么颜色，那么我们倒着来处理染色。
可是如何判断当前要染的区间是否在之前就被染过色了？
用并查集！！
f[i]表示i到f[i]-1这段区间已经被染过色了，那么我们把i染过色之后，f[i]=i+1。
处理一段区间，只要一直顺着f[i]染就可以了~
#include <iostream>#include <cstring>#include <algorithm>#include <cstdio>#define M 10000000+5using namespace std;int f[M],n,m,p,q,c[M];int Getfather(int x){if (f[x]==x||!f[x])return f[x]=x;return f[x]=Getfather(f[x]);}int main(){scanf("%d%d%d%d",&n,&m,&p,&q);int tot=0;for (int i=m;i;i–){int l=((long long)i*p+q)%n+1,r=((long long)i*q+p)%n+1;if (l>r) swap(l,r);for (int k=Getfather(l);k<=r;k=Getfather(k)){c[k]=i;tot++;f[k]=k+1;}if (tot==n) break;}for (int i=1;i<=n;i++)printf("%d\n",c[i]);return 0;}
感悟：
1.RE是因为没有处理f[n]=n+1
2.并查集维护区间信息~
生活若剥去了理想梦想幻想，那生命便只是一堆空架子
