四重解法---P1047 校门外的树

题目描述

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

输入输出格式

输入格式：

输入文件tree.in的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

输出格式：

输出文件tree.out包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

输入输出样例

输入样例#1：

500 3

150 300

100 200

470 471

输出样例#1：

298

说明

NOIP2005普及组第二题

对于20%的数据，区域之间没有重合的部分；

对于其它的数据，区域之间有重合的情况。

分析

四种解法，不解释

#include<bits/stdc++.h>  //1层----模拟流

using namespace std;

int n,m,ans;

bool a[11000];

int read()

{

    int x=0,f=1;char c=getchar();

    while(!isdigit(c) && c!='-') c=getchar();

    if(c=='-') f=-1,c=getchar();

    while(isdigit(c)) x=x*10+c-'0',c=getchar();

    return x*f;

}

int main()

{

    n=read()+1;m=read();

    while(m--)

    {

        int l=read(),r=read();

        for(int i=l;i<=r;++i)

            a[i]=1;     //表示已被砍

    }

    for(int i=0;i<=n;++i)

        if(a[i]) ++ans;

    printf("%d\n",n-ans);

    return 0;

}

这里是分割线

#include<bits/stdc++.h>  //2层----忘了是什么算法来着，反正比模拟高级

using namespace std;

int n,m,ans;

int a[11000],f[11000];

int read()

{

    int x=0,f=1;char c=getchar();

    while(!isdigit(c) && c!='-') c=getchar();

    if(c=='-') f=-1,c=getchar();

    while(isdigit(c)) x=x*10+c-'0',c=getchar();

    return x*f;

}

int main()

{

    n=read()+1;m=read();  //代码需要，就+1了，下同

    while(m--)

    {

        int l=read()+1,r=read()+1;

        ++a[l];--a[r+1];

    }

    for(int i=1;i<=n;++i)

    {

        f[i]=f[i-1]+a[i];

        if(f[i]) ++ans; //被砍过，ans++

    }

    printf("%d\n",n-ans);

    return 0;

}

这里是分割线

#include<bits/stdc++.h>  //3层----树状数组(比线段树好打一些)

using namespace std;

int n,m,f[11000],ans;

/*         本代码以树状数组区间加，单点查询为模板            */

int read()

{

    int x=0,f=1;char c=getchar();

    while(!isdigit(c) && c!='-') c=getchar();

    if(c=='-') f=-1,c=getchar();

    while(isdigit(c)) x=x*10+c-'0',c=getchar();

    return x*f;

}

int lowbit(int x)

{

    return x&(-x);

}

void update(int i,int x)

{

    for(;i<=n;i+=lowbit(i))

        f[i]+=x;

}

bool query(int i)

{

    int res=0;

    for(;i;i-=lowbit(i))

        if(f[i]) res+=f[i];

    return res;

}

int main()

{

    n=read()+1;m=read(); //注意题目中的树范围是0~n，

    //树状数组的操作是从1开始的，所以n++

    while(m--)

    {

        int l=read()+1,r=read()+1; //同上+1

        update(l,1);

        update(r+1,-1);

    }

    for(int i=1;i<=n;++i)

        if(query(i)) ++ans;   //被砍过，ans++ 

    printf("%d\n",n-ans); 

    return 0;

}

这里是分割线

#include<bits/stdc++.h>  //4层----线段树

using namespace std;

int n,m,sum[41000];

//姑且写个读入优化吧，虽说其实用不着

int read()

{

    int x=0,f=1;char c=getchar();

    while(!isdigit(c) && c!='-') c=getchar();

    if(c=='-') f=-1,c=getchar();

    while(isdigit(c)) x=x*10+c-'0',c=getchar();

    return x*f;

}

void buildtree(int k,int l,int r)

{

    if(l==r){ sum[k]=1; return ;}

    if(l>r) return ;

    int mid=l+r>>1;

    buildtree(k*2,l,mid);

    buildtree(k*2+1,mid+1,r);

    sum[k]=sum[k*2]+sum[k*2+1];

}

void update(int k,int l,int r,int L,int R)

{

    if(l>R || r<L || !sum[k]) return ;  //不包含直接退

    if(L<=l && r<=R)    //全包含sum改0

    {

        sum[k]=0;

        return ;

    }

    int mid=l+r>>1;

    update(k*2,l,mid,L,R);

    update(k*2+1,mid+1,r,L,R);

    sum[k]=sum[k*2]+sum[k*2+1]; //更新sum[father];

}

int main()

{

    n=read();m=read();

    buildtree(1,0,n);

    while(m--)

    {

        int l,r;

        l=read();r=read();

        update(1,0,n,l,r);

    }

    printf("%d\n",sum[1]);

    return 0;

}

                                                            --all by Mr Zhang

ok，四种解法发完。

（你会几种？_ (:зゝ∠) _）

测试平台

落谷P1047

巴特西

四重解法---P1047 校门外的树

题目描述

输入输出格式

输入输出样例

说明

分析

测试平台

最新文章

热门文章