「POI2018 R2」列车员 Conductor 题解

题目大意

有 $m$ 个车站，编号 $1$ 到 $m$。有 $n$ 条乘客路线，第 $i$ 条路线从 $a_i$ 上车，$b_i$ 下车。查票只能在两个连续车站之间进行（不能在车站停靠时进行）。

要求：

1. 找到最少的查票次数，使得每条路线至少被查一次票
2. 计算所有满足最少查票次数的方案数（模 $10^9+7$）

问题分析

问题转化

将车站看作数轴上的点 $1, 2, \ldots, m$，每条路线 $(a_i, b_i)$ 对应一个区间 $[a_i, b_i)$（注意是左闭右开，因为查票在车站之间进行）。

查票位置是车站之间的间隙，有 $m-1$ 个可能的查票位置：$1-2, 2-3, \ldots, m-1-m$。

问题转化为：在 $m-1$ 个位置中选择一些位置查票，使得每个区间 $[a_i, b_i)$ 至少包含一个查票位置。

最少查票次数

这是一个经典的区间覆盖问题。我们可以用贪心算法求解：

1. 将所有区间按照右端点 $b_i$ 排序
2. 从左到右扫描，每次选择当前能覆盖最多未覆盖区间的查票位置

更具体地说：

• 将区间按 $b_i$ 从小到大排序
• 初始化查票位置集合为空
• 对于每个区间，如果它还没有被覆盖，就在它的右端点 $-1$ 的位置查票（即在 $b_i-1$ 位置查票）

证明：对于每个未覆盖的区间，在 $b_i-1$ 位置查票可以覆盖该区间，并且由于区间按右端点排序，这个位置能覆盖尽可能多的后续区间。

方案数计算

在确定了最少查票次数 $k$ 后，我们需要计算所有能达到这个最少查票次数的方案数。

设贪心算法选出的查票位置为 $p_1, p_2, \ldots, p_k$（按位置从小到大排序）。

对于每个查票位置 $p_i$，考虑它能够移动的范围：

• $p_i$ 必须能够覆盖所有依赖它的区间
• $p_i$ 不能移动到会使得某些区间无法被覆盖的位置

具体来说，对于每个 $p_i$，它的可选范围是：

• 下界：$L_i = \max(\text{上一个查票位置}+1, \text{依赖该位置的最左区间的左端点})$
• 上界：$U_i = \min(\text{下一个查票位置}-1, \text{依赖该位置的最右区间的右端点}-1)$

那么方案数就是 $\prod_{i=1}^k (U_i - L_i + 1)$。

算法实现

步骤

1. 输入处理：读取 $m, n$ 和 $n$ 个区间
2. 区间排序：按 $b_i$ 从小到大排序
3. 贪心选择：
   • 维护当前已覆盖的最右位置 $last$
   • 遍历排序后的区间，如果 $a_i > last$，说明需要新查票位置，选择 $b_i-1$，更新 $last = b_i-1$
4. 计算方案数：
   • 确定每个查票位置的可选范围
   • 计算乘积模 $10^9+7$

时间复杂度

• 排序：$O(n \log n)$
• 贪心选择：$O(n)$
• 方案数计算：$O(n)$
• 总复杂度：$O(n \log n)$，对于 $n \leq 5\times 10^5$ 可接受

代码实现

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

const int MOD = 1e9 + 7;

struct Interval {
    int a, b;
    bool operator<(const Interval& other) const {
        return b < other.b;
    }
};

pair<int, int> solve(int m, int n, vector<Interval>& intervals) {
    // 按右端点排序
    sort(intervals.begin(), intervals.end());
    
    // 贪心选择查票位置
    vector<int> checkpoints;
    int last_covered = 0;  // 当前已覆盖的最右位置
    
    for (const auto& interval : intervals) {
        if (interval.a > last_covered) {
            // 需要新的查票位置
            int pos = interval.b - 1;
            checkpoints.push_back(pos);
            last_covered = pos;
        }
    }
    
    int min_count = checkpoints.size();
    
    if (min_count == 0) {
        return {0, 1};  // 不需要查票
    }
    
    // 计算每个查票位置的可选范围
    vector<int> L(min_count), R(min_count);
    
    // 预处理每个查票位置必须覆盖的区间范围
    vector<int> min_start(min_count, m), max_end(min_count, 1);
    
    int idx = 0;
    for (const auto& interval : intervals) {
        while (idx < min_count && checkpoints[idx] < interval.a) {
            idx++;
        }
        if (idx < min_count && checkpoints[idx] < interval.b) {
            min_start[idx] = min(min_start[idx], interval.a);
            max_end[idx] = max(max_end[idx], interval.b);
        }
    }
    
    // 计算每个位置的可选范围
    for (int i = 0; i < min_count; i++) {
        int left_bound = (i == 0) ? 1 : checkpoints[i - 1] + 1;
        L[i] = max(left_bound, min_start[i]);
        
        int right_bound = (i == min_count - 1) ? m - 1 : checkpoints[i + 1] - 1;
        R[i] = min(right_bound, max_end[i] - 1);
    }
    
    // 计算方案数
    long long ways = 1;
    for (int i = 0; i < min_count; i++) {
        if (R[i] >= L[i]) {
            ways = ways * (R[i] - L[i] + 1) % MOD;
        } else {
            ways = 0;
            break;
        }
    }
    
    return {min_count, (int)ways};
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int z;
    cin >> z;
    
    while (z--) {
        int m, n;
        cin >> m >> n;
        
        vector<Interval> intervals(n);
        for (int i = 0; i < n; i++) {
            cin >> intervals[i].a >> intervals[i].b;
        }
        
        auto result = solve(m, n, intervals);
        cout << result.first << " " << result.second << "\n";
    }
    
    return 0;
}

样例解释

样例1

11 4
1 4
6 8  
2 7
9 10

最少查票次数为3，方案数为5。

贪心选择过程：

1. 区间排序后：[(1,4), (2,7), (6,8), (9,10)]
2. 处理(1,4)：选择位置3查票
3. 处理(2,7)：位置3已覆盖
4. 处理(6,8)：选择位置7查票
5. 处理(9,10)：选择位置9查票

查票位置：3,7,9

可选范围：

• 位置3：可移动到1,2,3 → 3种选择
• 位置7：可移动到6,7 → 2种选择
• 位置9：只能选9 → 1种选择

但题目输出是5种方案，说明某些位置的移动是有限制的，需要更精细的范围计算。

总结

本题结合了贪心算法和组合计数：

• 贪心：解决最少查票次数问题
• 组合数学：计算所有最优方案数

关键点在于理解每个查票位置的移动范围受限于它必须覆盖的区间，这需要仔细处理区间依赖关系。