刷题总结——纸带（NOIP赛前模拟）

题目：

　　有一个无限长的纸带··上面被划分为若干个格子··现在进行N次操作，第i次操作在L到R上擦出曾经写上的数字（如果有）,并写上数字i，询问最终可以看到多少个数字

　　N小于10^6

题解：

　　首先毫无疑问离散化,但注意离散化时候如果相邻两个数的差大于1··需要在中间插入一个在两数之间的数···不然会错··

　　然后正常的方法可以线段树来搞··然而可能被卡常··

　　最快的方法同时也是最巧的方法：并查集，我们将询问倒着来··然后用并查集维护每次染色的最右端的位置,具体实现看代码,可以证明为O（n）的复杂度

代码：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<cctype>

#include<string>

#include<cstring>

#include<algorithm>

using namespace std;

inline int R(){

    char c;int f=;

    for(c=getchar();c<''||c>'';c=getchar());

    for(;c<=''&&c>='';c=getchar())    f=(f<<)+(f<<)+c-'';

    return f;

}

const int N=4e6+;

struct node{int l,r;}q[N];

bool visit[N];

int n,b[N*],cnt=,father[N*],ans;

inline int get(int a){

    if(father[a]==a)    return a;

    else return father[a]=get(father[a]);

}

int main()

{

    //freopen("a.in","r",stdin);

    n=R();

    for(int i=,x,y;i<=n;i++)    x=R(),y=R(),q[i].l=x+,q[i].r=y,b[++cnt]=x+,b[++cnt]=y;

    sort(b+,b+cnt+);cnt=unique(b+,b+cnt+)-b-;int temp=cnt;

    for(int i=;i<=cnt;i++)

        if(b[i-]+!=b[i])    b[++temp]=b[i-]+;

    cnt=temp;sort(b+,b+cnt+);cnt=unique(b+,b+cnt+)-b-;

    for(int i=;i<=cnt;i++)    father[i]=i;

    for(int i=;i<=n;i++)    q[i].l=lower_bound(b+,b+cnt+,q[i].l)-b,q[i].r=lower_bound(b+,b+cnt+,q[i].r)-b;

    for(int i=n;i>=;i--){

        bool flag=false;

        for(int pre=,pos=q[i].l;pos<=q[i].r;pos++){

            if(pre)    father[pre]=pos;

            if(!visit[pos])    pre=pos,visit[pos]=true,flag=true;

            else pre=pos,pos=get(pos);

        }

        if(flag)  ans++;

    }

    cout<<ans<<endl;

    return ;

}

巴特西

刷题总结——纸带（NOIP赛前模拟）

题目：

题解：

代码：

最新文章

热门文章