開啟寶盒 題解｜APCS 2023 年 6 月高級 第 4 題
前置知識
這題是拓撲排序那套「計數歸零才出列」的技巧，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：
- 拓撲排序（用佇列、數入度）：NTUCPC Guide〈拓撲排序〉——「每個點記還有幾條邊沒處理、歸零才放進佇列」，那一頁的習題正是本題；吳邦一《AP325》第 7 章的拓樸順序（教材 PDF 第 246～247 頁）用 in-degree 陣列寫了同一套非遞迴版本。
- 佇列與 BFS：NTUCPC Guide〈廣度優先搜尋〉——「拿到新東西就放進佇列、從前端一個一個處理」的骨架；
queue的用法在〈Stack、Queue 與 Deque〉。 - vector 的陣列：
vector<vector<int>>記「每種鑰匙被哪些寶盒需要」，每列長度不一樣也沒關係。
簡潔題意
\(n\) 個寶盒、\(m\) 種鑰匙（編號 \(0\) 到 \(m-1\)）。每個寶盒要同時擁有指定的 \(k\) 種鑰匙才能打開，打開後得到盒裡的 \(k\) 種鑰匙；鑰匙拿到就永遠有、不會用掉。一開始有 \(t\) 種鑰匙，問最多能打開幾個寶盒（\(1 \le n, m \le 10^5\)，\(1 \le k \le \min(5, m)\)，\(0 \le t \le m\)；每種鑰匙最多被 \(60\) 個寶盒列為開啟條件）。
依正確通過的測試資料筆數給分，其中：
- 子題組 1（\(20\) 分）：\(n, m \le 100\)，\(k = 1\)。
- 子題組 2（\(20\) 分）：\(k = 1\)。
- 子題組 3（\(60\) 分）：無額外限制。
先拿下 20 分：一輪一輪掃，掃到沒有新盒子可開
鑰匙不會用掉，所以開得了的盒子開了永遠不吃虧——不用考慮先開哪個，只要把開得了的都開掉就好。最直接的做法：把全部寶盒掃一遍，需要的鑰匙都有就開、把新鑰匙記下來；只要這一輪有開到新盒子，就再掃一輪，直到一整輪都沒有新進展。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, k, t;
cin >> n >> m >> k >> t;
vector<bool> have(m, false); // have[x]：手上有沒有鑰匙 x
for (int i = 0; i < t; i++) {
int x;
cin >> x;
have[x] = true;
}
vector<vector<int>> need(n, vector<int>(k)), give(n, vector<int>(k));
for (int i = 0; i < n; i++)
for (int j = 0; j < k; j++) cin >> need[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < k; j++) cin >> give[i][j];
vector<bool> opened(n, false);
int count = 0;
bool changed = true;
while (changed) { // 一輪下來沒開任何新盒子才停
changed = false;
for (int i = 0; i < n; i++) {
if (opened[i]) continue;
bool ok = true;
for (int j = 0; j < k; j++)
if (!have[need[i][j]]) ok = false;
if (ok) {
opened[i] = true;
count++;
changed = true;
for (int j = 0; j < k; j++) have[give[i][j]] = true;
}
}
}
cout << count << '\n';
return 0;
}
每一輪至少開一個盒子才會繼續，最多 \(n\) 輪、每輪 \(O(nk)\)，\(n \le 100\) 沒問題；但寶盒串成一條長鏈（每輪只開得了一個）時是 \(O(n^2 k)\)，\(n = 10^5\) 的鏈本站實測 \(17\) 秒。子題組 1 的 \(20\) 分穩穩到手。
從 20 分到 40 分：k = 1 時，寶盒就是鑰匙之間的箭頭
\(k = 1\) 時每個寶盒只有一個條件、給一把鑰匙，把它看成「鑰匙 \(a\) → 鑰匙 \(b\)」的箭頭：有了 \(a\) 就開得了這個盒子、拿到 \(b\)。問題變成從起初的鑰匙出發，沿箭頭能走到哪些鑰匙——BFS。反過來記錄 boxesOf[x]＝需要鑰匙 \(x\) 的寶盒有哪些，從佇列拿出鑰匙 \(x\) 時，boxesOf[x] 裡的寶盒全部打開、沒拿過的新鑰匙放進佇列。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, k, t;
cin >> n >> m >> k >> t; // 這個子題組 k = 1
vector<bool> have(m, false);
queue<int> q; // 拿到了、但還沒拿去開盒子的鑰匙
for (int i = 0; i < t; i++) {
int x;
cin >> x;
have[x] = true;
q.push(x);
}
vector<int> need(n), give(n);
for (int i = 0; i < n; i++) cin >> need[i];
for (int i = 0; i < n; i++) cin >> give[i];
vector<vector<int>> boxesOf(m); // boxesOf[x]：需要鑰匙 x 的寶盒有哪些
for (int i = 0; i < n; i++) boxesOf[need[i]].push_back(i);
int count = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i : boxesOf[x]) { // 有了 x，這些寶盒全部打得開
count++;
if (!have[give[i]]) { // 新鑰匙才入列：每種鑰匙只處理一次
have[give[i]] = true;
q.push(give[i]);
}
}
}
cout << count << '\n';
return 0;
}
每種鑰匙進佇列一次、每個寶盒被看一次，\(O(n + m)\)。注意答案是寶盒數：好幾個寶盒都只要鑰匙 \(0\) 時，它們各算一個。範例 2 是 \(k = 2\)，不是這份程式讀得懂的格式（會印 8），子題組 1、2 的 \(40\) 分穩穩到手。
從 40 分到 100 分：每個寶盒記「還缺幾種」
\(k \ge 2\) 時一個寶盒要集齊 \(k\) 種鑰匙才開得了。骨架不變，只多一個計數：missing[i] 一開始是 \(k\)，每處理一種它需要的鑰匙就減一，減到 \(0\) 的那一刻才算開盒、才把盒裡的新鑰匙放進佇列——跟拓撲排序裡「入度減到 \(0\) 才出列」一模一樣。圖 1 是範例 2 跑完的樣子：佇列依序處理 \(6, 5, 2, 0, 7, 1\) 六種鑰匙，鑰匙 \(3\)、\(4\) 永遠拿不到，需要它們的五個寶盒「還缺」停在 \(1\)。
每種鑰匙只進佇列一次，所以要用 have[y] 擋掉已經拿過的鑰匙——同一把鑰匙處理兩次，需要它的寶盒就會被多扣一次、少一把也開了。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, k, t;
cin >> n >> m >> k >> t;
vector<bool> have(m, false);
queue<int> q; // 拿到了、但還沒拿去開盒子的鑰匙
for (int i = 0; i < t; i++) {
int x;
cin >> x;
have[x] = true;
q.push(x);
}
vector<vector<int>> boxesOf(m); // boxesOf[x]：需要鑰匙 x 的寶盒有哪些
vector<int> missing(n, k); // missing[i]：寶盒 i 還缺幾種鑰匙
for (int i = 0; i < n; i++)
for (int j = 0; j < k; j++) {
int x;
cin >> x;
boxesOf[x].push_back(i);
}
vector<vector<int>> give(n, vector<int>(k));
for (int i = 0; i < n; i++)
for (int j = 0; j < k; j++) cin >> give[i][j];
int count = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i : boxesOf[x]) { // 每個需要 x 的寶盒少缺一種
missing[i]--;
if (missing[i] == 0) { // 湊齊了：開盒
count++;
for (int y : give[i])
if (!have[y]) { // 新鑰匙才入列：每種鑰匙只處理一次
have[y] = true;
q.push(y);
}
}
}
}
cout << count << '\n';
return 0;
}
每種鑰匙處理一次，每個寶盒的 \(k\) 個條件各被扣一次，\(O(nk + m)\)；\(n = m = 10^5\)、\(k = 5\) 本站實測 \(0.2\) 秒。「每種鑰匙最多被 \(60\) 個寶盒需要」只是保證 boxesOf 的總長度不會爆，寫法上不用特別處理。
測過再交：範例沒有「重複拿到同一把鑰匙」
兩個範例蓋到了開盒順序與輸入順序不同（範例 1）、\(k = 2\) 要集齊（範例 2）。沒蓋到：一開始一把鑰匙都沒有、盒子給的鑰匙早就有了、好幾個寶盒要同一把鑰匙、最長的鏈。
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
1 1 1 ／ 1 0 ／ 0 ／ 0 |
1 |
最小輸入：盒子給的是已經有的鑰匙，照樣算開了一個 |
1 2 1 ／ 0 ／ 1 ／ 0 |
0 |
一開始一把鑰匙都沒有（\(t = 0\)）：答案 \(0\) |
3 2 1 ／ 1 0 ／ 0 ／ 0 ／ 0 ／ 1 ／ 1 ／ 1 |
3 |
三個寶盒都只要鑰匙 \(0\)：答案是寶盒數，數鑰匙會印 2 |
3 4 1 ／ 1 0 ／ 2 ／ 1 ／ 0 ／ 3 ／ 2 ／ 1 |
3 |
要開的順序跟輸入順序剛好相反：只掃一輪會印 1 |
2 3 2 ／ 2 0 1 ／ 0 1 ／ 0 2 ／ 0 1 ／ 1 2 |
1 |
寶盒 \(0\) 給的鑰匙早就有了：重複放進佇列會把寶盒 \(1\) 的「還缺」多扣一次、印 2 |
| 用程式造：\(n = m = 10^5\)、\(k = 5\)，一開始有 \(0\)～\(4\)，寶盒 \(i\) 需要 \(i\)～\(i+4\)、給 \(i+1\)～\(i+5\)，\(n\) 個寶盒依相反順序輸入 | 100000 |
最大測資兼最長的鏈：逐輪掃描的版本 \(30\) 秒跑不完，滿分版 \(0.2\) 秒 |
六筆都親眼看過正確，這題就穩了。
常犯錯誤
- 只掃一輪：要開的順序跟輸入順序不一定一樣，範例 1 印
2、範例 2 印4。 - 拿到任何一把需要的鑰匙就開：\(k \ge 2\) 要全部集齊，範例 2 印
20（每個寶盒被數了兩次）。 - 開了盒子忘了把裡面的鑰匙拿出來用：範例 1 印
2、範例 2 印2。 - 已經有的鑰匙又放進佇列：同一把鑰匙處理兩次，需要它的寶盒「還缺」被多扣一次、少一把也開了，範例 2 印
10。 - \(k = 1\) 時數「拿到幾種鑰匙」：答案是寶盒數，自測表第 3 列印
2。