秒，秒啊……

很容易想到线段树，但是在[tex]N=10^6,M=10^7[/tex]的情况下，线段树肯定会TLE。

考虑修改，我们可以发现真正影响一个馒头颜色的只是作用于此馒头上的最后一个操作。可以考虑倒序枚举操作，然后暴力修改。但是如此暴力修改的话可能覆盖了实际时间线较晚的操作……

考虑并查集！每个节点修改完后将其父亲改为下一个点，这样的话被修改的地方就可以轻松跳过了。

注意一个细节，第[tex]N[/tex]个馒头被染色后，其父亲会被修改为[tex]N+1[/tex]，所以说并查集实际上要开[tex]N+1[/tex]！

代码：

/**************************************************************
    Problem: 2054
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2476 ms
    Memory:39796 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1000005;
int Color[maxn];
int P[maxn];
int n;
int find_set(int x){
    if(P[x]==x)
        return x;
    else
        return P[x]=find_set(P[x]);
}
inline void init_set(){
    register int i;
    for(i=1;i<=(n+1);i++)
        P[i]=i;
}
int buf[20];
inline void PutInt(int x){
    register int i,p=0;
    if(x==0){
        buf[p++]=0;
    }else{
        while(x){
            buf[p++]=x%10;
            x/=10;
        }
    }
    for(i=p-1;i>=0;i--)
        putchar(buf[i]+'0');
    putchar('\n');
}
int main(){
    int m,p,q;
    register int i,j,l,r,k=0;
    bool OK=false;
    scanf("%d%d%d%d",&n,&m,&p,&q);
    init_set();
    for(i=m;i>=1;i--){
        l=(((i%n)*(p%n))%n+q%n)%n+1;
        r=(((i%n)*(q%n))%n+p%n)%n+1;
        if(l>r)
            swap(l,r);
        for(j=find_set(l);j<=r;j=find_set(j)){
            Color[j]=i;
            P[j]=j+1;
            k++;
            if(k==n){
                OK=true;
                break;
            }
        }
        if(OK)
            break;
    }
    for(i=1;i<=n;i++)
        PutInt(Color[i]);
    return 0;
}

• 相关文章
• 全局相关文章