# APCS實作題2024年10月第4題：搭到終點 > 日期：2024年10月31日 > 作者：王一哲 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=o714) <br /> ## 題目 ### 問題描述 有一個數線從 $0$ 到 $m$，你一開始在位置 $0$ 上，想要搭公車到位置 $m$ 處。 有 $n$ 台公車路線可以選擇，每一公車路線都有其行駛的起點和終點。 例如你想要到位置 $m = 9$，且有 $n = 5$ 條公車路線如下 | 公車路線編號 | 1 | 2 | 3 | 4 | 5 | | --------- | -- | -- | -- | -- | -- | | 路線起終點 | [0, 4] | [4, 6] | [0, 6] | [3, 7] | [5, 9] | 你可以任意地決定公車何時出發，並且在公車的路線範圍內都可以上車，但一定會搭到該路線的終點才下車，且不可在同一位置同時上下車。 你想知道總共有幾種搭車方式可以到位置 $m$。如上述例子總共有 $7$ 種搭車方式，分別如下列： 1. 1 -> 2 -> 4 -> 5 (先搭乘路線 $1$ 到位置 $4$，再搭乘路線 2 到位置 $6$，接著搭乘路線4 到位置 $7$，最後搭乘路線 5 到位置 $9$) 2. 1 -> 2 -> 5 3. 1 -> 3 -> 4 -> 5 4. 1 -> 3 -> 5 5. 1 -> 4 -> 5 6. 3 -> 4 -> 5 7. 3 -> 5 由於搭乘方式數量可能很大，請輸出搭乘方式數量 mod $p$ 的結果。 <br /> ### 輸入格式 第一行有三個正整數 $n, m, p ~(1 \leq n \leq 2 \times 10^5,~ 1 \leq m \leq 10^9,~ 1 \leq p \leq 10^9 + 9)$ 代表有 $n$ 個公車路線，終點在 $m$ 以及答案要 mod 的整數 $p$。 接下來一行有 $n$ 個數字，代表每一個公車路線的起始位置。 最後一行有 $n$ 個數字，代表每一個公車路線的終點位置。 子題配分 - 20%：$1 \leq n, m \leq 100$ - 40%：$1 \leq m \leq 10^5$ - 40%：無限制 <br /> ### 輸出格式 輸出共有幾種公車搭乘方式，由於答案數字可能很大，請輸出答案 mod $p$ 的結果。 <br /> ### 範例輸入1 ``` 5 9 11 0 4 0 3 5 4 6 6 7 9 ``` ### 範例輸出1 ``` 7 ``` ### 範例輸入2 ``` 6 8 4 0 1 2 3 5 6 3 6 6 6 8 8 ``` ### 範例輸出2 ``` 2 ``` <br /> ## Python 程式碼 吳邦一教授的寫法，來源[在此](https://hackmd.io/@bangyewu/rJ5yJqEe1x#%E7%AC%AC%E5%9B%9B%E9%A1%8C-%E6%90%AD%E5%88%B0%E7%B5%82%E9%BB%9E-ZeroJudge-o714)，我想不到更好的寫法。 費時最久約 0.9 s，使用記憶體最多 52 MB，通過測試。 ```python= from bisect import bisect_left n, m, p = map(int, input().split()) # 公車路線數 n，目的地在 m，答案取 p 的餘數 start = list(map(int, input().split())) # 公車起點 end = list(map(int, input().split())) # 公車終點 seg = sorted(zip(end, start)) # 合併公車終點、起點，以終點排序 dp = [1] # 到達各站的搭法數量前綴和，到達起點 0 搭法有 1 種 point = [0] # 最後所在的車站編號 for en, st in seg: # 依序讀取各路線的起點、終點 if point[-1] != en: # 如果這輛公車的的終點不等於 point 最後一項 point.append(en) # 更新 point dp.append(dp[-1]) # 更新 dp if st == 0: # 如果這輛公車的起點是 0 dp[-1] = (dp[-1] + dp[-2]) % p # dp[-1] 的數量要再加上到此站之前所有的搭法數量 else: # 其它狀況 i = bisect_left(point, st) - 1 # 用二分搜尋法從 point 之中找 st 插入的索引值再減 1 dp[-1] = (dp[-1] + dp[-2] - dp[i] + p) % p # 前面全部的總和減去前i站的總合，取餘數 # end of for loop if point[-1] != m: ans = 0 # 搭不到目的地，答案為 0 else: ans = (dp[-1] - dp[-2] + p) % p # 更新答案 print(ans) ``` <br /><br /> ## C++ 程式碼 費時最久約 0.4 s，使用記憶體最多 6.1 MB，通過測試。 ```cpp= #include <iostream> #include <vector> #include <utility> #include <algorithm> typedef long long LL; using namespace std; int main() { int n, m, p; cin >> n >> m >> p; // 公車路線數 n，目的地在 m，答案取 p 的餘數 vector<pair<int, int>> seg (n); // 公車終點、起點 for(int i=0; i<n; i++) cin >> seg[i].second; for(int i=0; i<n; i++) cin >> seg[i].first; sort(seg.begin(), seg.end()); // 以終點排序 vector<LL> dp = {1}; // 到達各站的搭法數量前綴和，到達起點 0 搭法有 1 種 vector<int> point = {0}; // 最後所在的車站編號 for(int i=0; i<n; i++) { // 依序讀取各路線的起點、終點 int en = seg[i].first, st = seg[i].second; if (point.back() != en) { // 如果這輛公車的的終點不等於 point 最後一項 point.push_back(en); // 更新 point dp.push_back(dp.back()); // 更新 dp } if (st == 0) { // 如果這輛公車的起點是 0 dp[dp.size()-1] = (dp[dp.size()-1] + dp[dp.size()-2]) % p; // dp[dp.size()-1] 的數量要再加上到此站之前所有的搭法數量 } else { // 其它狀況 int i = lower_bound(point.begin(), point.end(), st) - point.begin() - 1; // 用二分搜尋法從 point 之中找 st 插入的索引值再減 1 dp[dp.size()-1] = (dp[dp.size()-1] + dp[dp.size()-2] - dp[i] + p) % p; // 前面全部的總和減去前i站的總合，取餘數 } } int ans; if (point.back() != m) ans = 0; // 搭不到目的地，答案為 0 else ans = (dp[dp.size()-1] - dp[dp.size()-2] + p) % p; // 更新答案 cout << ans << "\n"; return 0; } ``` <br /><br /> --- ###### tags:`APCS`、`Python`、`C++`