洛谷P1047-校门外的树(模拟)

简介: 洛谷P1047-校门外的树(模拟)

题目描述:


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


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


输入:


第一行有222个整数L(1≤L≤10000)L(1 \le L \le 10000)L(1≤L≤10000)和M(1≤M≤100) M(1 \le M \le 100)M(1≤M≤100),LLL代表马路的长度,MMM代表区域的数目,LLL和MMM之间用一个空格隔开。

接下来的MMM行每行包含222个不同的整数,用一个空格隔开,表示一个区域的起始点和终止点的坐标。


输出:  


1个整数,表示马路上剩余的树的数目。


样例输入:


500 3

150 300

100 200

470 471


样例输出:


298


说明/提示:


NOIP2005普及组第二题

对于2020%20的数据,区域之间没有重合的部分;

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


程序代码:


#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 10001
int x[N];
int main()
{
    int l,m,sum,a,b,i,j;
    cin>>l>>m;
  memset(x,0,sizeof(x));
    for(i=1;i<=m;i++)
  {
    cin>>a>>b;
    for(j=a;j<=b;j++)
    {
      x[j]=1;
    }
  }
  for(i=0;i<=l;i++)
  {
    if(x[i]==0)
      sum++;
  }
  cout<<sum<<endl;
  return 0;
}
相关文章
|
5月前
|
C++
【洛谷 P1047】[NOIP2005 普及组] 校门外的树 题解(位集合)
**NOIP2005普及组问题:**给定长度为$l$的马路,上面等距种植着树,需移除位于建造地铁区域的树。输入包含马路长度和区域数,以及各区域起止点,输出移树后剩余树的数量。样例输入:$l=500$, $m=3$,输出:$298$。$20\%$数据无区域重合,$1 \leq l \leq 10^4$,$1 \leq m \leq 100$。解决方案利用位集合(bitset)表示树的状态,遍历区域将树设为0,最后统计1的数量。AC代码使用C++实现。
26 0
|
算法 Android开发 C++
LeetCode 周赛上分之旅 #49 再探内向基环树
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
88 1
|
6月前
校门外的树
校门外的树
21 0
|
算法 Android开发 Kotlin
LeetCode 周赛上分之旅 #42 当 LeetCode 考树上倍增,出题的趋势在变化吗
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
115 0
LeetCode 周赛上分之旅 #42 当 LeetCode 考树上倍增,出题的趋势在变化吗
校门外的树(三种解法,非直接暴力)
校门外的树(三种解法,非直接暴力)
|
算法
【过河卒】回溯算法保姆式解题
【过河卒】回溯算法保姆式解题
90 0
|
算法 C++ Python
【每日算法Day 68】脑筋急转弯:只要一行代码,但你会证吗?
【每日算法Day 68】脑筋急转弯:只要一行代码,但你会证吗?
113 0
|
算法 Java
洛谷新手村算法题分析
本文汇总洛谷新手村算法题的分析解答,题目代码基本由Java实现。
112 0
洛谷新手村算法题分析
蓝桥杯历届试题 蚂蚁感冒(模拟版+非模拟版)
长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左,有的朝右。   每只蚂蚁都只能沿着杆子向前爬,速度是1厘米/秒。   当两只蚂蚁碰面时,它们会同时掉头往相反的方向爬行。   这些蚂蚁中,有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时,会把感冒传染给碰到的蚂蚁。   请你计算,当所有蚂蚁都爬离杆子时,有多少只蚂蚁患上了感冒。 输入格式   第一行输入一个整数n (1 < n < 50), 表示蚂蚁的总数。   接着的一行是n个用空格分开的整数 Xi (-100< Xi < 100), Xi的绝对值, 表示蚂蚁离开杆子左边端点的距离。正值表示头朝右,负值表示头朝左, 数据中不会出现0值,也不会出
204 1
蓝桥杯历届试题 蚂蚁感冒(模拟版+非模拟版)
|
项目管理
第321场周赛赛后总结(前三题)+记录一道有意思的题目
前言 今天早上可能是浏览器出了点故障,一直没法打开力扣官网页面(但别的页面没问题)(别人都能进说明不是官网服务器的问题咯),错过了周赛(不过就算按时参加估计也是陪跑,就先这么安慰自己了),下午发现能进去了,赶紧找个时间补了一下题。
124 0