校運代表隊 題解|APCS 2026 年 3 月中高級 第 3 題
前置知識
這題的核心是用遞迴一個一個決定隊員,下面的講解直接把這些當成已知,沒讀過的先讀:
- 遞迴:NTUCPC Guide〈遞迴〉——函式呼叫自己,把問題交給規模小一點的自己處理。
- 用遞迴枚舉,不合法就不往下走:吳邦一《AP325》第 1 章「遞迴」的 P-1-7「子集合乘積」用遞迴一個一個決定每個數選不選;P-1-9「N-Queen 解的個數」一列一列放皇后,跟前面衝突的位置直接跳過(站上題目 ap325p107、ap325p109)。這題「選完一位隊員,再從下一個編號開始選下一位」也是同一個架構。
- 字典序:NTUCPC Guide〈枚舉〉的「字典序比較」——兩個數列從頭比,第一個不一樣的位置誰比較小,那個數列就比較小。
簡潔題意
\(m\) 個班、每班 \(r\) 人,候選人依班級順序編號 \(1 \sim mr\)(第 \(1 \sim r\) 號是第一班,依此類推),每人有一項專長(編號 \(1 \sim n\))。選 \(k\) 人組隊,要求專長兩兩不同、每班至多兩人。隊伍成員依編號由小到大排列,所有合法隊伍依字典序排序,輸出第 \(t\) 隊(\(1 \le n \le 9\),\(1 \le m \le 17\),\(1 \le r \le 4\),\(1 \le k \le 5\),保證第 \(t\) 隊存在)。
依正確通過的測試資料筆數給分,其中:
- 子題組 1(\(40\) 分):\(r = 1\)。
- 子題組 2(\(60\) 分):無額外限制。
枚舉的順序剛好就是字典序
隊伍要依成員編號遞增排列再比字典序,所以先決定編號最小的隊員、再決定第二小的……遞迴每一層都從小到大試下一個人:第一個人選 \(1\) 的所有隊伍會先被產生,然後才是第一個人選 \(2\) 的……產生出來的順序自然就是字典序。產生到第 \(t\) 支合法隊伍就輸出、停止。
先拿下 40 分:\(r = 1\),選滿 \(k\) 人再檢查專長
每班只有一個人,「每班至多兩人」一定成立,只要檢查專長有沒有重複。候選人最多 \(17\) 個,\(\binom{17}{5} = 6188\) 種組合全部產生、每一種選滿之後再檢查,都來得及。
#include <iostream>
using namespace std;
int n, m, r, k;
long long t; // 還要再跳過幾支隊伍;數到 0 就是要輸出的那一隊
int total; // 候選人總數 m * r
int skill[69]; // skill[i]:第 i 位候選人(1-base)的專長
int chosen[5]; // 目前選到的隊員編號(遞增)
// 選滿 k 人之後才檢查專長有沒有重複(r = 1:每班一人,「每班至多兩人」一定成立)
bool valid() {
bool skill_used[10] = {};
for (int i = 0; i < k; i++) {
if (skill_used[skill[chosen[i]]]) return false;
skill_used[skill[chosen[i]]] = true;
}
return true;
}
// 已經選了 picked 人,下一位從編號 start 開始往後挑。找到第 t 隊就回傳 true。
bool search(int picked, int start) {
if (picked == k) {
if (!valid()) return false;
t--;
if (t > 0) return false; // 還沒輪到,繼續找下一隊
for (int i = 0; i < k; i++) cout << chosen[i] << (i + 1 == k ? '\n' : ' ');
return true;
}
for (int i = start; i <= total; i++) {
chosen[picked] = i;
if (search(picked + 1, i + 1)) return true;
}
return false;
}
int main() {
cin >> n >> m >> r >> k >> t;
total = m * r;
for (int i = 1; i <= total; i++) cin >> skill[i];
search(0, 1);
return 0;
}
⚠️ 兩個範例的 \(r\) 都是 \(4\),這個版本對範例會 WA 是正常的;子題組 1 的 \(8\) 筆全對,穩拿 \(40\) 分。
從 40 分到 100 分:多檢查每班人數,而且邊選邊檢查
\(r\) 可以到 \(4\) 之後,多了「每班至多兩人」:第 \(i\) 位候選人屬於第 \(\lfloor (i - 1) / r \rfloor\) 班(從 \(0\) 數起),每班記一個人數。
其實把這個檢查也加進最後的 valid() 就會對:\(mr\) 最多 \(68\) 人,\(\binom{68}{5} \approx 1.04 \times 10^7\) 種組合、每種檢查 \(5\) 個人,約 \(5 \times 10^7\) 步,C++ 在時限內跑得完。不過更好的寫法是選的當下就檢查:
- 這個人的專長已經有人用了 → 跳過(用一個布林陣列記錄哪些專長用掉了)。
- 這個人的班級已經選了兩人 → 跳過。
- 剩下的候選人不夠湊滿 \(k\) 人 → 迴圈提早結束。
這樣遞迴只會走到「目前為止都合法」的前綴,產生出來的每一支隊伍都是合法的,不用再檢查,數到第 \(t\) 支就輸出。遞迴回來的時候,要把剛剛記下的專長和班級人數改回去,才能換下一個人試。
#include <iostream>
using namespace std;
int n, m, r, k;
long long t; // 還要再跳過幾支隊伍;數到 0 就是要輸出的那一隊
int total; // 候選人總數 m * r
int skill[69]; // skill[i]:第 i 位候選人(1-base)的專長
bool skill_used[10]; // 專長是否已被隊上的人用掉
int class_count[18]; // 每班已經選了幾人
int chosen[5]; // 目前選到的隊員編號(遞增)
// 已經選了 picked 人,下一位從編號 start 開始往後挑。找到第 t 隊就回傳 true。
bool search(int picked, int start) {
if (picked == k) {
t--;
if (t > 0) return false; // 還沒輪到,繼續找下一隊
for (int i = 0; i < k; i++) cout << chosen[i] << (i + 1 == k ? '\n' : ' ');
return true;
}
int need = k - picked; // 還要選幾人:剩下的候選人不夠就不用試了
for (int i = start; i + need - 1 <= total; i++) {
int c = (i - 1) / r; // 第 i 位候選人屬於第 c 班(0-base)
if (skill_used[skill[i]] || class_count[c] == 2) continue;
skill_used[skill[i]] = true;
class_count[c]++;
chosen[picked] = i;
if (search(picked + 1, i + 1)) return true;
skill_used[skill[i]] = false;
class_count[c]--;
}
return false;
}
int main() {
cin >> n >> m >> r >> k >> t;
total = m * r;
for (int i = 1; i <= total; i++) cin >> skill[i];
search(0, 1);
return 0;
}
測過再交:範例沒有 \(k = 1\),也沒有 \(t = 1\)
兩個範例的 \(r\) 都是 \(4\),\(t\) 分別是 \(2\) 和 \(536\)。沒蓋到的:只選一人、輸出第一隊、只有一個班、最大的輸入。
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
5 4 1 1 3 / 2 2 1 5 |
3 |
\(k = 1\):每個人自己就是一隊,第 \(t\) 隊就是第 \(t\) 號(子題組 1 版就能驗) |
3 1 3 2 2 / 1 1 2 |
2 3 |
只有一班,第 \(1\)、\(2\) 號專長相同:1 2 不合法,合法的只有 1 3、2 3 |
6 2 3 3 1 / 1 2 3 4 5 6 |
1 2 4 |
專長全不同、\(t = 1\):1 2 3 三人同班,不合法 |
用程式造:9 17 4 5 3029568 / 專長 1 2 3 4 5 6 7 8 9 1 2 3 … 輪流排滿 \(68\) 人 |
60 63 64 67 68 |
最大的輸入,\(t\) 是最後一隊(一共 \(3029568\) 支合法隊伍) |
四筆都親眼看過正確,這題就穩了。
常犯錯誤
- 每班上限差一(寫成
class_count[c] == 3才跳過,等於允許三人同班):範例 1 印1 2 4。 - 班級算錯(\(1\)-base 的編號直接
i / r):第 \(r\)、\(2r\)、\(3r\)……號被算到下一班,範例 1 印1 2 8。 - 數到第 \(t\) 隊的判斷差一(先看
t > 0再減,等於輸出第 \(t + 1\) 隊):範例 1 印1 3 7。 - 「剩下的人不夠」的界線差一(寫成
i + need <= total):含最後一號候選人的隊伍全被跳過,範例 1 印1 3 7。 - 遞迴回來忘了把專長和班級人數改回去:兩個範例都什麼都沒印。