第十一届全国青少年信息学（计算机）奥林匹克联赛复赛试题 （普及组）答案及解析.pdfVIP

一、实操题

1、陶陶摘苹果

【问题描述】

陶陶家的院子里有一棵苹果树，每到秋天树上就会结出10个苹果。苹果成熟的时候

，陶陶就会跑去摘苹果。陶陶有个30厘米高的板凳，当她不能直接用手摘到苹果的

时候，就会踩到板凳上再试试。

现在已知10个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，

请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。

【输入文件】

输入文件apple.in包括两行数据。第一行包含10个100到200之间（包括100和200）

的整数（以厘米为单位）分别表示10个苹果到地面的高度，两个相邻的整数之间用

一个空格隔开。第二行只包括一个100到120之间（包含100和120）的整数（以厘米

为单位），表示陶陶把手伸直的时候能够达到的最大高度。

【输出文件】

输出文件apple.out包括一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的

数目。

【样例输入】

100200150140129134167198200111

110

【样例输出】

5

参考答案：陶陶能够摘到的苹果的数目为5。

解析：【喵呜刷题小喵解析】：

首先，我们需要读取输入文件apple.in中的两行数据。第一行包含10个苹果到地面

的高度，第二行表示陶陶把手伸直的时候能够达到的最大高度。

然后，我们需要遍历这10个苹果的高度，判断陶陶能否摘到每个苹果。具体地，我

们需要比较每个苹果的高度和陶陶的最大高度。如果某个苹果的高度小于等于陶陶

的最大高度，那么陶陶就能够摘到这个苹果。

最后，我们统计陶陶能够摘到的苹果的数目，并将结果输出到输出文件apple.out中

。

对于样例输入，10个苹果的高度分别为100,200,150,140,129,134,167,198,200,

111，陶陶的最大高度为110。陶陶能够摘到的苹果的高度分别为100,150,140,129,

111，因此陶陶能够摘到的苹果的数目为5。

2、校门外的树

【问题描述】

某校大门外长度为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包括一行，这一行只包含一个整数，表示马路上剩余的树的数目

。

【样例输入】

5003

150300

100200

470471

【样例输出】

298

【数据规模】

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

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

参考答案：对于这个问题，我们可以使用差集的思想来解决。首先，统计马路上原

本有多少棵树，即L+1棵。然后，对于每个区域，统计该区域覆盖了多少棵树。最

后，将马路上原本有的树的数量减去所有区域覆盖的树的数量，即可得到马路上剩

余的树的数目。具体实现时，我们可以使用一个变量total_trees来保存马路上原本

有的树的数量，初始值为L+1。对于每个区域，我们可以计算该区域的长度，即终

止点坐标减去起始点坐标，然后将其加1（因为区域端点处的两棵树也要被覆盖）

，得到一个变量region_trees。然后，将region_trees从total_trees中减去，即可得到

该区域覆盖的树的数量。最后，将所有区域覆盖的树的数量累加起来，即为所有区

域覆盖的树的总数量。最后，将马路上原本有的树的数量减去所有区域覆盖的树的

总数量，即可得到马路上剩余的树的数目。

解析：【喵呜刷题小喵解析】：

这个问题可以使用差集的思想来解决。差集是指两个集合的差，即在一个集合中但

不在另一个集合中的元素。在这个问题中，我们可以将马路上原本有的树看作一个

集合，将每个区域覆盖的树看作另一个集合。我们需要找出这两个