题解 P2391 【白雪皑皑】

Sky_star · 2017-09-08 12:54:42 · 题解

这道题可以用并查集来打（然而我一开始脑抽竟然用了双向链表-.-），从最后开始往前进行涂色，因为显然后面的优先级大于前面，后面的会将前面涂的颜色覆盖。这样我们只要快速查找下一个没被涂的点就行了，因此我想到了并查集，只要保证每个集合的fa没被涂过就行了。这样就避免了复杂度过高。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXN 1001000
using namespace std;
int mp[MAXN],fa[MAXN],n,m,p,q;
int find(int x){return (fa[x]<0)?x:fa[x]=find(fa[x]);}
int main()
{
    scanf("%d%d%d%d",&n,&m,&p,&q);
    memset(fa,-1,sizeof fa);
    for(int i=m;i>=1;i--)
    {
        int mi=(i*p+q)%n+1,ma=(i*q+p)%n+1;//这里的操作要注意下因为m为10000000，所以尽量减少多余的操作
        if(mi>ma)swap(mi,ma);
        mi=find(mi);
        while(mi<=ma)mp[mi]=i,fa[mi]=mi+1,mi=find(mi+1);
    }
    for(int i=1;i<=n;i++)printf("%d\n",mp[i]);
    return 0;
}