题解 | #小A的线段（easy version）#

题目链接

题目描述

在坐标轴的整数点 $1, \dots, m$ 上给出 $n$ 条闭区间线段，第 $i$ 条线段用其端点 $[l_i, r_i]$ 描述。

现在要从这 $n$ 条线段中选择若干条，使得每个整数点被至少两条所选线段覆盖。求满足条件的选择方案数量。

两种方案视为不同，当且仅当存在某条线段在两方案中的“选不选”状态不同。答案对 $10^9 + 7$ 取模。

解题思路

本题要求我们从 $n$ 条线段中选出若干条，使得 $[1, m]$ 中的每个整数点都被至少两条线段覆盖，并计算满足条件的方案总数。

这是一个组合计数问题。由于 $n$ 的范围通常不大（例如 $n \le 20$ ），我们可以考虑使用搜索算法来遍历所有可能的线段选择组合。一个朴素的方案是枚举 $2^n$ 种选择，然后对每一种选择，都检查是否满足覆盖条件。但每次检查都需要 $\mathcal{O}(n \cdot m)$ 的时间，总复杂度太高。

为了优化检查过程，我们可以采用 扫描线 (Sweep-line) 算法进行预处理，并结合 回溯搜索 (Backtracking) 进行剪枝。

1. 扫描线预处理

扫描线的核心思想是将二维的区间问题转化为一维的事件点问题。

事件点: 对于每条线段 $[l_i, r_i]$ ，我们将其拆分为两个事件：在坐标 $l_i$ 处有一个“线段开始”事件，在坐标 $r_i$ 处有一个“线段结束”事件。
排序: 我们将所有 $2n$ 个事件点按坐标从小到大排序。
离散化与分段: 排序后的事件点会将坐标轴 $[1, m]$ 分割成一系列“基本区间”。在任意一个基本区间内部（不含端点），覆盖它的线段数量是恒定的。
信息统计: 我们可以通过一次遍历（扫描）这些事件点，来高效地计算出每个基本区间的覆盖数，以及每个事件点本身的覆盖情况。我们将这些信息存储在一个数组 coverage_info 中，其中每个元素记录 [坐标点, 到下一个坐标点之间的覆盖数, 在此坐标点开始的线段数, 在此坐标点结束的线段数]。

2. 回溯搜索 (DFS)

在预处理得到所有线段都选择时，整个坐标轴的覆盖信息后，我们就可以开始进行回溯搜索。代码采用了一种巧妙的逆向思路：

初始状态: 假设我们选择了全部 $n$ 条线段。利用扫描线算法计算出这种全选状态下的 coverage_info。
初始剪枝: 如果在全选的情况下，仍然存在某个整数点覆盖数小于 2，那么无论如何删除线段，都不可能满足条件。此时答案直接为 0。
递归过程: 定义 dfs(k, coverage_info)，表示我们正在考虑是否要删除第 $k$ 条线段，coverage_info 是基于保留 $0, \dots, k-1$ 条线段（以及 $k, \dots, n-1$ 也暂时保留）的覆盖信息。
- 决策1：保留第 $k$ 条线段 我们不对 coverage_info 做任何改动，直接递归调用 dfs(k+1, coverage_info)，将返回的结果计入总方案数。
- 决策2：删除第 $k$ 条线段 a. 我们从当前的 coverage_info 中“减去”第 $k$ 条线段 $[l_k, r_k]$ 的贡献，得到一个新的 new_coverage_info。 b. 合法性检查 (剪枝)：检查这个 new_coverage_info 是否依然满足“所有整数点覆盖数至少为 2”的条件。 c. 如果检查通过，说明删除第 $k$ 条线段是可行的，我们递归调用 dfs(k+1, new_coverage_info)，将返回的结果也计入总方案数。 d. 如果检查不通过，说明删除第 $k$ 条线段后导致了不满足题意的覆盖情况，那么基于这个决策的所有后续方案都是无效的。我们剪掉这个分支，不进行递归。
递归出口: 当 k == n 时，说明我们已经对所有 $n$ 条线段都做出了“保留”或“删除”的决策，并且每一步都满足覆盖条件。这对应一种合法的方案，返回 1。

最终，dfs(0, initial_coverage_info) 的返回值就是题目的答案。

变量名说明: 题目描述中使用 $n$ 代表线段数量， $m$ 代表坐标范围。代码中，输入时 m 对应线段数量， $n$ 对应坐标范围。为了忠于原始代码逻辑，我们的实现也遵循代码的变量命名。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

// 题目描述中的 n, m 在代码中分别用 m, n 表示
int max_coord, num_segments;
vector<pair<int, int>> edges;
long long MOD = 1e9 + 7;

// 严格按照Python代码的逻辑进行有效性检查
bool is_valid(const vector<vector<long long>>& n_r) {
    if (n_r.size() <= 2) { // 至少需要有起点和终点
        for (const auto& row : n_r) {
            if (row[1] < 2) return false;
        }
        return true;
    }
    for (size_t i = 1; i < n_r.size() - 1; ++i) {
        if (((n_r[i][1] + n_r[i][3]) < 2) ||
            (n_r[i][1] < 2 && (n_r[i + 1][0] - n_r[i][0]) > 2)) {
            return false;
        }
    }
    if (n_r.back()[3] < 2) {
        return false;
    }
    return true;
}

long long dfs(int seg_idx, vector<vector<long long>> n_r) {
    if (seg_idx >= num_segments) {
        return 1;
    }

    // 方案1: 保留第 seg_idx 条线段
    long long count = dfs(seg_idx + 1, n_r);

    // 方案2: 尝试删除第 seg_idx 条线段
    pair<int, int> edge_to_remove = edges[seg_idx];
    
    // 严格按照Python代码逻辑更新 n_r
    for (size_t i = 1; i < n_r.size(); ++i) {
        if (n_r[i][0] == edge_to_remove.first) {
            n_r[i][2]--;
        }
        if (n_r[i][0] == edge_to_remove.second) {
            n_r[i][3]--;
        }
        if (n_r[i][0] >= edge_to_remove.first && n_r[i][0] < edge_to_remove.second) {
            n_r[i][1]--;
        }
    }

    if (is_valid(n_r)) {
        count = (count + dfs(seg_idx + 1, n_r)) % MOD;
    }

    return count;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> max_coord >> num_segments;
    edges.resize(num_segments);
    
    struct Boundary {
        int coord;
        int type; // 0 for start, 1 for end
    };
    vector<Boundary> boundaries;

    for (int i = 0; i < num_segments; ++i) {
        cin >> edges[i].first >> edges[i].second;
        boundaries.push_back({edges[i].first, 0});
        boundaries.push_back({edges[i].second, 1});
    }

    sort(boundaries.begin(), boundaries.end(), [](const Boundary& a, const Boundary& b) {
        if (a.coord != b.coord) return a.coord < b.coord;
        return a.type < b.type;
    });

    vector<vector<long long>> initial_coverage;
    initial_coverage.push_back({0, 0, 0, 0});
    
    // 严格按照Python代码的逻辑构建 initial_coverage
    size_t cov_idx = 0;
    for(const auto& b : boundaries) {
        if (b.type == 0) { // start
            if (b.coord == initial_coverage[cov_idx][0]) {
                initial_coverage[cov_idx][1]++;
                initial_coverage[cov_idx][2]++;
            } else {
                initial_coverage.push_back({(long long)b.coord, initial_coverage[cov_idx][1] + 1, 1, 0});
                cov_idx++;
            }
        } else { // end
            if (b.coord == initial_coverage[cov_idx][0]) {
                initial_coverage[cov_idx][1]--;
                initial_coverage[cov_idx][3]++;
            } else {
                 initial_coverage.push_back({(long long)b.coord, initial_coverage[cov_idx][1] - 1, 0, 1});
                 cov_idx++;
            }
        }
    }

    if (!is_valid(initial_coverage)) {
        cout << 0 << endl;
        return 0;
    }

    cout << dfs(0, initial_coverage) << endl;

    return 0;
}

import java.util.*;

public class Main {
    static int maxCoord, numSegments;
    static int[][] edges;
    static final long MOD = 1_000_000_007L;

    // 严格按照Python代码的逻辑进行有效性检查
    static boolean isValid(List<long[]> n_r) {
        if (n_r.size() <= 2) {
            for (long[] row : n_r) {
                if (row[1] < 2) return false;
            }
            return true;
        }
        for (int i = 1; i < n_r.size() - 1; i++) {
            if (((n_r.get(i)[1] + n_r.get(i)[3]) < 2) ||
                (n_r.get(i)[1] < 2 && (n_r.get(i + 1)[0] - n_r.get(i)[0]) > 2)) {
                return false;
            }
        }
        if (n_r.get(n_r.size() - 1)[3] < 2) {
            return false;
        }
        return true;
    }

    static long dfs(int segIdx, List<long[]> n_r) {
        if (segIdx >= numSegments) {
            return 1;
        }

        // 方案1: 保留
        List<long[]> keep_n_r = new ArrayList<>();
        for (long[] row : n_r) {
            keep_n_r.add(row.clone());
        }
        long count = dfs(segIdx + 1, keep_n_r);

        // 方案2: 删除
        int[] edgeToRemove = edges[segIdx];
        
        for (int i = 1; i < n_r.size(); i++) {
            long[] info = n_r.get(i);
            if (info[0] == edgeToRemove[0]) {
                info[2]--;
            }
            if (info[0] == edgeToRemove[1]) {
                info[3]--;
            }
            if (info[0] >= edgeToRemove[0] && info[0] < edgeToRemove[1]) {
                info[1]--;
            }
        }

        if (isValid(n_r)) {
            count = (count + dfs(segIdx + 1, n_r)) % MOD;
        }

        return count;
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        maxCoord = sc.nextInt();
        numSegments = sc.nextInt();
        edges = new int[numSegments][2];

        List<int[]> boundaries = new ArrayList<>();
        for (int i = 0; i < numSegments; i++) {
            edges[i][0] = sc.nextInt();
            edges[i][1] = sc.nextInt();
            boundaries.add(new int[]{edges[i][0], 0}); // 0: start
            boundaries.add(new int[]{edges[i][1], 1}); // 1: end
        }
        
        boundaries.sort((a, b) -> {
            if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
            return Integer.compare(a[1], b[1]);
        });

        List<long[]> initialCoverage = new ArrayList<>();
        initialCoverage.add(new long[]{0, 0, 0, 0});

        int covIdx = 0;
        for (int[] b : boundaries) {
            if (b[1] == 0) { // start
                if (b[0] == initialCoverage.get(covIdx)[0]) {
                    initialCoverage.get(covIdx)[1]++;
                    initialCoverage.get(covIdx)[2]++;
                } else {
                    initialCoverage.add(new long[]{b[0], initialCoverage.get(covIdx)[1] + 1, 1, 0});
                    covIdx++;
                }
            } else { // end
                if (b[0] == initialCoverage.get(covIdx)[0]) {
                    initialCoverage.get(covIdx)[1]--;
                    initialCoverage.get(covIdx)[3]++;
                } else {
                    initialCoverage.add(new long[]{b[0], initialCoverage.get(covIdx)[1] - 1, 0, 1});
                    covIdx++;
                }
            }
        }

        if (!isValid(initialCoverage)) {
            System.out.println(0);
            return;
        }

        System.out.println(dfs(0, initialCoverage));
    }
}

import sys

# 增加递归深度限制
sys.setrecursionlimit(2000)

# n_coord: 坐标范围, m_seg: 线段数量
n_coord, m_seg = map(int, sys.stdin.readline().split())
edges = [list(map(int, sys.stdin.readline().split())) for _ in range(m_seg)]
MOD = 10**9 + 7

# 1. 扫描线预处理
boundary = []
for i, e in enumerate(edges):
    boundary.append([e[0], 0, i]) # 0 表示起点
    boundary.append([e[1], 1, i]) # 1 表示终点

boundary.sort()

# num 数组: [坐标, 该点覆盖数, 该点起点数, 该点终点数]
# 严格按照用户提供的原始逻辑构建
num = [[0, 0, 0, 0]]
i = 0
for b in boundary:
    coord, type, _ = b
    if type == 0: # start
        if coord == num[i][0]:
            num[i][1] += 1
            num[i][2] += 1
        else:
            num.append([coord, num[i][1] + 1, 1, 0])
            i += 1
    else: # end
        if coord == num[i][0]:
            num[i][1] -= 1
            num[i][3] += 1
        else:
            num.append([coord, num[i][1] - 1, 0, 1])
            i += 1

# 2. 回溯搜索 (DFS)
# 严格按照用户提供的原始逻辑进行检查
def is_valid(n_r):
    if len(n_r) <= 2:
        for row in n_r:
            if row[1] < 2: return False
        return True
    for i in range(1, len(n_r) - 1):
        if ((n_r[i][1] + n_r[i][3]) < 2) or \
           (n_r[i][1] < 2 and (n_r[i + 1][0] - n_r[i][0]) > 2):
            return False
    if n_r[-1][3] < 2:
        return False
    return True

memo = {}
def dfs(ind, n_r_tuple):
    if ind >= m_seg:
        return 1
    
    state = (ind, n_r_tuple)
    if state in memo:
        return memo[state]

    n_r = [list(row) for row in n_r_tuple]

    # 决策1: 保留
    res = dfs(ind + 1, tuple(map(tuple, n_r)))

    # 决策2: 删除
    e = edges[ind]
    # 严格按照用户提供的原始逻辑更新
    for i in range(1, len(n_r)):
        if n_r[i][0] == e[0]:
            n_r[i][2] -= 1
        if n_r[i][0] == e[1]:
            n_r[i][3] -= 1
        if n_r[i][0] >= e[0] and n_r[i][0] < e[1]:
            n_r[i][1] -= 1

    if is_valid(n_r):
        res = (res + dfs(ind + 1, tuple(map(tuple, n_r)))) % MOD
    
    memo[state] = res
    return res

# 3. 初始状态检查与调用
if not is_valid(num):
    print(0)
else:
    initial_num_tuple = tuple(map(tuple, num))
    print(dfs(0, initial_num_tuple))

算法及复杂度

算法：扫描线 + 回溯搜索 (DFS) + 记忆化
时间复杂度：预处理阶段，对 $2n$ 个端点进行排序，时间复杂度为 $\mathcal{O}(n \log n)$ (其中 $n$ 是线段数)。回溯搜索阶段，由于状态由 (当前线段索引, 覆盖信息数组) 决定，状态空间巨大。但有效状态（满足覆盖条件）的数量可能有限，通过记忆化搜索可以避免重复计算。最坏情况下，时间复杂度仍接近 $\mathcal{O}(2^n \cdot n^2)$ ，但在实际数据中表现会更好。
空间复杂度：扫描线和覆盖信息数组需要 $\mathcal{O}(n)$ 的空间。记忆化哈希表和DFS的递归深度可能导致空间复杂度较高，最坏可达 $\mathcal{O}(2^n \cdot n^2)$ 。