华师一附中OI组

标题: P1047 校门外的树 [打印本页]
作者: admin    时间: 2018-4-19 14:18
标题: 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%的数据，区域之间没有重合的部分；

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

作者: xpb    时间: 2018-4-20 21:08
  1. #include<iostream>
  2. using namespace std;
  3. const int mn=10001;
  4. int l,m,s[mn],e[mn],k[mn],i,j,numb;
  5. int main()
  6. {
  7.     cin>>l>>m;
  8.     for(i=1; i<=m; i++)
  9.     {
  10.         cin>>s[i]>>e[i];
  11.     }
  12.     for(i=0; i<=l; i++)
  13.     {
  14.         k[i]=1;
  15.     }
  16.     for(i=1; i<=m; i++)
  17.     {
  18.         for(j=s[i]; j<=e[i]; j++)
  19.         {
  20.             k[j]=0;
  21.         }
  22.     }
  23.     for(i=0; i<=l; i++)
  24.     {
  25.         if(k[i]==1)
  26.         {
  27.             numb++;
  28.         }
  29.     }
  30.     cout<<numb;
  31.     return 0;
  32. }
复制代码
作者: 张笑宇    时间: 2018-4-22 21:03
本帖最后由 张笑宇 于 2018-4-22 21:05 编辑
  1. <div class="blockcode"><blockquote>#include<iostream>
  2. using namespace std;
  3. const int mx=10010;
  4. int a[mx],b[mx],c[mx];
  5. int i,j;
  6. int l,n;
  7. int main()
  8. {
  9.     cin>>l>>n;
  10.     for (i=1;i<=n;i++) cin>>a[i]>>b[i];
  11.     for (i=0;i<=mx-1;i++) c[i]=true;
  12.     for (i=1;i<=n;i++)
  13.     {
  14.         for (j=a[i];j<=b[i];j++) c[j]=false;
  15.     }
  16.     int sum=0;
  17.     for (i=0;i<=l;i++) if (c[i]==true) sum++;
  18.     cout<<sum;
  19.     return 0;
  20. }
复制代码

作者: GTR    时间: 2018-5-4 23:07
程序：
#include <iostream>
using namespace std;
int l,m;
int main ()
{
cin>>l>>m;
int *p=new int [l+1];
for(int i=0;i<l+1;i++)
*(p+i)=1;
for(int i=0;i<m;i++)
{
int t1,t2;
cin>>t1>>t2;
for(int j=t1;j<=t2;j++)
*(p+j)=0;
}
int count=0;
for(int i=0;i<l+1;i++)
if(*(p+i)) count++;
cout<<count<<endl;
return 0;
}
作者: WJL    时间: 2018-5-25 23:01
  1. #include <iostream>
  2. using namespace std;
  3. int main ()
  4. {
  5. int l,m;
  6. cin>>l>>m;
  7. int *p=new int [l+1];
  8. for(int i=0;i<l+1;i++)
  9. *(p+i)=1;
  10. for(int i=0;i<m;i++)
  11. {
  12. int temp1,temp2;
  13. cin>>temp1>>temp2;
  14. for(int j=temp1;j<=temp2;j++)
  15. *(p+j)=0;
  16. }
  17. int count=0;
  18. for(int i=0;i<l+1;i++)
  19. if(*(p+i)) count++;
  20. cout<<count<<endl;
  21. return 0;
  22. }
复制代码
作者: 倚窗倾听风吹雨    时间: 2018-6-27 21:34
  1. #include<iostream>
  2. using namespace std;
  3. int l,m,i,j,s=0;
  4. int main()
  5. {
  6.     cin>>l>>m;
  7.     int a,b,t[l];
  8.     for(i=0;i<=l;i++)
  9.         t[i]=1;
  10.     for(i=0;i<=m-1;i++)
  11.      {
  12.        cin>>a>>b;
  13.        for(j=a;j<=b;j++)
  14.         t[j]=0;
  15.      }  
  16.     for(i=0;i<=l;i++)
  17.         if(t[i]==1)s++;
  18.     cout<<s;
  19.     return 0;

  21. }
复制代码
作者: universehyf    时间: 2018-6-30 23:57
#include<iostream>
using namespace std;
int a[10001]={};
int main()
{
        int m,n,d,b,c=0;
        cin>>m>>n;
        for(int i=1;i<=n;i++)
        {
                cin>>d>>b;
                for(int j=d;j<=b;j++) a[j]=1;
        }
        for(int i=0;i<=m;i++)
                if(!a[i]) ++c;
        cout<<c;
        return 0;
}



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2