（洛谷）题目题号P1047 [NOIP2005 普及组] 校门外的树

Hello大家好我是小亦，这是今天发布的第二篇题解，唉我就在想怎么样才能把粉丝提上来呢隔壁朋友都比我高了好多唉苦恼qwq，好吧接受现实，好那么好今天我们来讲的是来自于NOIP2005年普及组的真题名叫：校门外的树，其实这道题跟其他几道题很相似，应该是同一家的吧qwq，好了不废话了思路给大家qwq：

首先呢这道是让我求模拟的题目，已下为个人步骤，如果有误请指出：

1. 初始化数组：创建一个长度为 l+1 的数组 trees，其中每个元素的初始值设为1，表示每棵树最初都是存在的。

2. 读取输入：读取马路的长度 l 和区域的数目 m。

3. 标记区域：对于每个区域，读取起始点和终止点的坐标 u 和 v。将 trees 数组中从 u 到 v（包括端点）的元素值设为0，表示这些位置的树将被移除。

4. 计算剩余树的数量：遍历 trees 数组，统计值为1的元素数量，即未被标记为移除的树。

5. 输出结果：输出剩余树的总数。

详细步骤：

• 初始化：使用一个布尔数组 trees 来表示每棵树的存在状态。数组的索引代表树的位置，从0到 ll。

• 处理区域：对于每个区域，我们通过将数组中相应位置的值设置为0来“移除”树。

• 统计剩余树：遍历数组，计算值为1的元素数量，这些元素代表未被移除的树。

• 输出：输出剩余树的总数。

优化考虑：

• 空间优化：由于题目中 l 的最大值可以达到 10的4次方，使用一个长度为 l+1 的数组是可行的。但是，如果l 非常大，我们可以考虑使用一个更紧凑的数据结构，如位图或哈希集合，来减少空间消耗。

• 时间优化：在标记区域时，我们可以通过一次遍历将一个连续的区间设置为0，而不是逐个元素设置，这样可以减少操作次数。

• 处理重叠区域：题目中提到区域之间可能有重合的部分，这意味着一些树可能被多次标记为移除。在我们的方法中，这不会构成问题，因为我们只关心最终哪些树被移除，而不关心它们被标记了多少次。

通过这种方法，我们可以有效地计算出在移除指定区域的树之后，马路上剩余的树的数量,好了写完思路了，希望大家能听懂，话不多说贴代码qwq：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int l, m;
    cin >> l >> m;
    vector<int> trees(l + 1, 1); // 初始化数组，所有位置都有树

    // 处理每个区域
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        for (int j = u; j <= v; ++j) {
            trees[j] = 0; // 将区域内的树标记为0
        }
    }

    // 计算剩余的树的数量
    int remaining_trees = 0;
    for (int i = 0; i <= l; ++i) {
        if (trees[i] == 1) {
            remaining_trees++;
        }
    }

    cout << remaining_trees << endl; // 输出结果
    return 0;
}

本人将注释与最完全的示例给大家，请放心食用~，完工