校门外的树

题目描述

马路长 $L$ （ $1\le L\le 10000$ ），数轴上整数点 $0,1,\dots,L$ 各种一棵树。给出 $M$ （ $1\le M\le 100$ ）个区域，每个用两个整数端点表示，端点顺序不保证、区间之间可能重合；移走每个区域内（含两端端点）的树，问还剩多少棵。

输入格式： 第一行 $L$ 和 $M$ ，接下来 $M$ 行每行一个区域的两个整数端点；输出格式： 一个整数，表示剩余的树数。 样例输入：

text

样例输出： 298。

思路

对每个整数点建一个删除标记，被区间覆盖就置 1；标记是幂等的，重叠区间重复置 1 不会多删，最后统计仍为 0 的点数即剩余树数。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 06:05
# update_at: 2026-10-02 06:05

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    length = next(data)  # 马路长 L，0..L 每个整数点一棵树
    m = next(data)       # 区域个数

    removed = bytearray(length + 1)  # 桶：1 = 该整数点的树已被移走
    for _ in range(m):
        start, end = next(data), next(data)
        lo, hi = sorted((start, end))  # 起止点顺序不保证，含两端端点
        removed[lo:hi + 1] = b'\x01' * (hi - lo + 1)  # 区间整体打标记

    print(removed.count(0))  # 仍为 0 的点就是留下来的树


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 13:26
 * update_at: 2026-10-06 13:27
 */

#include <cstdio>

typedef long long ll;

const int MAX_LENGTH = 10000; // 马路长度上限

char removed[MAX_LENGTH + 1]; // removed[i] 表示整数点 i 上的树已被移走（只有 0/1，用 char 控制内存）

int main() {
    ll length, region_count;
    scanf("%lld %lld", &length, &region_count);

    for (int region = 1; region <= region_count; region++) {
        ll start, end;
        scanf("%lld %lld", &start, &end);
        // 端点顺序不保证，先规范化成 [left_end, right_end]
        ll left_end = start;
        ll right_end = end;
        if (left_end > right_end) {
            left_end = end;
            right_end = start;
        }
        // 区间内的每个整数点（含两端端点）打删除标记，重复标记是幂等的
        for (ll point = left_end; point <= right_end; point++) {
            removed[point] = 1;
        }
    }

    ll remain = 0; // 一次都没被覆盖的树
    for (ll point = 0; point <= length; point++) {
        if (removed[point] == 0) {
            remain++;
        }
    }
    printf("%lld\n", remain);
    return 0;
}

目录

题目描述

思路

参考代码