P1047 校门外的树 题解(P1047 tree outside the school gate)

题目链接

这个题比较简单,怎么做都行,但是看洛谷后面题解感觉还是有点复杂了,所以随手写一写题解。

题目描述

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

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

输入格式

第一行有两个整数,分别表示马路的长度 $l $ 和区域的数目 m

接下来 m 行,每行两个整数 u, v,表示一个区域的起始点和终止点的坐标。

输出格式

输出一行一个整数,表示将这些树都移走后,马路上剩余的树木数量。

思路

最简单的是开一个数组,先种树再拔树,模拟。

然后这个题也可以用线段树。

后面还有用珂朵莉树的(没学过,不会)。

实际上这个题只需要遍历长度为\(l\)的数组一遍,复杂度\(O(l)\)。首先通过数组mp,在每个区域起始位置,记录下该区域的终点位置,也可以看成是在起始位置处打上了标记。在遍历数组时,用一个遍历suo维护当前被砍掉的树最远在哪。在没遇到标记时,树一定没有被砍。在遇到标记后,开始更新变量suo,如果当前位置小于suo则树一定被砍了,反之没有被砍。因此一层循环遍历就能数出剩余树木的数量。

AC代码

#include<bits/stdc++.h>
using namespace std;

int mp[10003];
int suo = -1;
int l,m;
int ans;

signed main()
{
    cin >> l >> m;
    for(int i=1;i<=m;++i)
    {
        int u,v;
        cin >> u >> v;
        mp[u] = v;
    }
    for(int i=0;i<=l;++i)
    {
        if(mp[i]&&mp[i]>suo)
        {
            suo = mp[i];
        }
        if(i<=suo){}
        else ans++;
    }
    cout << ans << endl;

	return 0;
}
————————

Title Link

This problem is relatively simple. You can do whatever you want, but it’s still a little complicated to look at the problem solution behind Luogu, so you can write it casually.

Title Description

There is a row of trees on the road with a length of \ (L \) outside the gate of a school, and the interval between each two adjacent trees is 11 meters. We can regard the road as a number axis. One end of the road is at the position of number axis 0 and the other end is at the position of $l $; Each integer point on the number axis, that is \ (0,1,2, \ dots, l \), has a tree.

Because there are some areas on the road to build subways. These areas are represented by their starting and ending points on the number axis. It is known that the coordinates of the starting point and ending point of any region are integers, and there may be overlapping parts between regions. Now move the trees in these areas (including the two trees at the end of the area). Your task is to calculate how many trees there are on the road after all these trees are removed.

Input format

The first line has two integers representing the length of the road $l $and the number of areas M

The next M lines, each with two integers u and V, represent the coordinates of the starting and ending points of a region.

Output format

Output an integer per line, indicating the number of trees remaining on the road after these trees are removed.

thinking

The simplest is to open an array, plant trees first, then pull them out, and simulate.

Then this problem can also be used as a line segment tree.

There’s also a Kodori tree behind it (I haven’t learned, I can’t).

In fact, this problem only needs to traverse the array with length \ (L \) once, with complexity \ (O (L) \). Firstly, through the array MP, the end position of each area is recorded at the starting position of each area, which can also be regarded as marking the starting position. When traversing the array, a traversal Suo is used to maintain the farthest location of the currently cut tree. The tree must not have been cut down when it did not meet the mark. After the tag is encountered, the variable Suo is updated. If the current position is less than Suo, the tree must be cut, otherwise it is not cut. Therefore, one layer of loop traversal can count the number of remaining trees.

AC code

#include<bits/stdc++.h>
using namespace std;

int mp[10003];
int suo = -1;
int l,m;
int ans;

signed main()
{
    cin >> l >> m;
    for(int i=1;i<=m;++i)
    {
        int u,v;
        cin >> u >> v;
        mp[u] = v;
    }
    for(int i=0;i<=l;++i)
    {
        if(mp[i]&&mp[i]>suo)
        {
            suo = mp[i];
        }
        if(i<=suo){}
        else ans++;
    }
    cout << ans << endl;

	return 0;
}