校運代表隊 題解|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。
  • 遞迴回來忘了把專長和班級人數改回去:兩個範例都什麼都沒印。