CF102D-Buses
题目大意：有m路公交车行驶在一个数轴上，给出每路公交车的起点和终点，所有公交车在起点和终点间的（整数）点都会停靠，停靠的时候可以上车，但只有每路公交的终点站能下车。要坐公交车从数轴的原点（即坐标为0的点）到坐标为n的点，问一共有多少种方法。
令dp[i]：在i点下车的方法数。不难想到，dp[i]的值就是将各路以i为终点的公交车沿途的可能方法数都加起来。
例如下列5路公交车
到达1的方法数为1，即dp[1] = 1
有两种方法到达2，第一种是坐第一路公交到达1，然后再在1上第二路公交到达2；另一种是直接坐第2路公交到达2；因此dp[2] = dp[1] + 1 = 2
到达3的方法数就比较多了，可以先坐第一、二路车到1或者2，然后再转车到3（如果到1的话还能先转车到2再到3）。最后可以算出到达3的方法数dp[3] = 8。
不难总结出：从0到达到达站i的方法数是将每一路以i为终点的车，从0到达这路车起点到终点间各个站的方法数都加起来。上面的dp[3]就是将第三路车经过的各个点——1和2，第四路车经过的各个点——1和2，以及第五路车经过的点2加起来，即dp[3]的数值等于dp[1] + dp[2] + dp[1] + dp[2] + dp[2]。可以通过前缀和来快速得出区间上各点的方法数。
还需要注意的是：这道题的数轴上的数值可能非常大，所以需要离散化处理。另外，如果要用到前缀和来求区间和的话，由于并不是每个离散化的点都是公车路线的终点，不能直接用前缀和下标-1来算，而应该找到待求点的前一个有效点。
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
46
47
48
49
50
51
52
53
54
55
56
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
pair<long long, long long> p[100005];
long long a[200005], dp[200005], s[200005];
const long long mod = 1e9 + 7;
int main()
{
int n, m, i, tot = 0;
long long x, y;
scanf("%d%d", &n, &m);
a[++tot] = 0;
a[++tot] = n;
for (i = 1; i <= m; i++)
{
scanf("%lld%lld", &x, &y);
a[++tot] = x;
a[++tot] = y;
p[i].first = y;
p[i].second = x;
}
sort(a + 1, a + 1 + tot);
n = unique(a + 1, a + 1 + tot) - a - 1;
for (i = 1; i <= m; i++)
{
p[i].first = lower_bound(a + 1, a + 1 + n, p[i].first) - a;
p[i].second = lower_bound(a + 1, a + 1 + n, p[i].second) - a;
}
sort(p + 1, p + 1 + m);
tot = 0;
a[++tot] = 1;
for (i = 1; i <= m; i++)
if (i < 2 || p[i].first != p[i - 1].first)
a[++tot] = p[i].first;
dp[1] = s[1] = 1;
for (i = 1; i <= m; i++)
{
x = lower_bound(a + 1, a + 1 + tot, p[i].second) - a - 1;
y = lower_bound(a + 1, a + 1 + tot, p[i].first) - a - 1;
dp[p[i].first] = (s[a[y]] - s[a[x]] + dp[p[i].first] + mod) % mod;
s[p[i].first] = (dp[p[i].first] + s[a[y]]) % mod;
}
printf("%lld", dp[n]);
return 0;
}
|