# APCS實作題2026年3月中高級第3題：校運代表隊 > 日期：2026年3月12日 > 作者：王一哲 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=s181) ## 題目 ### 問題描述 學校準備組建一支代表隊參加校運會。全校共有 $m$ 個班級，每個班級各派出 $r$ 位學生，因此總共有 $m \times r$ 位學生。學生們被統一編號，第 1 班的學生編號為 $1, 2, \dots, r$，第 2 班為 $r+1, r+2, \dots, 2r$，以此類推，第 $i$ 班的學生編號區間為 $[(i-1) \times r + 1, ir]$。 每位學生都擅長一種特定的比賽項目，共有 $n$ 種不同的項目。第 $i$ 位學生擅長的項目編號為 $a_i$。 校方希望從這 $m \times r$ 位學生中選出 $k$ 個人組成代表隊，並滿足以下嚴格條件： 1. **專長不重複**：這 $k$ 個人所擅長的項目必須互不相同。 2. **班級限額**：每個班級最多只能有 2 位學生被選入代表隊。 現在給定所有學生的專長項目以及整數 $t$，請找到所有合法組合中，學生編號組合字典序第 $t$ 小的方案。 <br /> ### 輸入說明 第一行包含五個整數 $n, m, k, r, t$ ($1 \leq n \leq 9, 1 \leq m \leq 17, 1 \leq r \leq 4, 1 \leq k \leq 5$)，$t$ 不超過合法組合數量。 第二行包含 $m \times r$ 個整數 $a_1, a_2, \dots, a_{m \times r}$ ($1 \leq a_i \leq n$)，代表每位學生的專長。 配分 - 40分：$r = 1$ - 60分：無限制。 <br /> ### 輸出格式 輸出一行包含 $k$ 個整數，代表第 $t$ 小組合中的學生編號。編號請按升序排列輸出。 <br /> ### 範例輸入1 ``` 5 2 4 3 2 3 1 2 4 1 3 1 5 ``` ### 範例輸出1 ``` 1 3 5 ``` ### 範例輸入2 ``` 8 10 4 5 536 5 5 8 2 3 1 1 3 7 8 2 7 4 1 5 7 7 5 2 1 6 7 7 8 4 7 5 3 2 7 8 4 2 5 3 6 7 8 8 6 ``` ### 範例輸出2 ``` 1 3 7 29 32 ``` <br /> ## Python 程式碼 這題考 DFS 與窮舉，要加上一些剪枝條件加速，以下的程式還有改進的空間。費時最久約為 0.9 s，使用記憶體最多約為 3 MB，通過測試。 ```python= import sys sys.setrecursionlimit(10000) n, m, r, k, t = map(int, input().split()) skills = [0] + list(map(int, input().split())) tot = m*r cnt = [0] def dfs(start, path, used_skill, class_cnt): if len(path) == k: cnt[0] += 1 if cnt[0] == t: print(*path) sys.exit(0) # 找到一組解就中止程式 return for i in range(start, tot+1): class_idx = (i-1)//r if class_cnt[class_idx] >= 2 or used_skill[skills[i]]: continue class_cnt[class_idx] += 1 used_skill[skills[i]] = True path.append(i) dfs(i+1, path, used_skill, class_cnt) class_cnt[class_idx] -= 1 used_skill[skills[i]] = False path.pop() dfs(1, [], [False]*(n+1), [0]*m) ``` <br /> 費時最久約為 0.9 s，使用記憶體最多約為 3 MB，通過測試。 ```python= import sys sys.setrecursionlimit(10000) data = sys.stdin.read().split() ptr = 0 n, m, r, k, t = map(int, data[ptr:ptr+5]) ptr += 5 tot = m*r skills = [0] + list(map(int, data[ptr:ptr+tot])) ptr += tot cnt = [0] def dfs(start, path, used_skill, class_cnt): if len(path) == k: cnt[0] += 1 if cnt[0] == t: res = " ".join(map(str, path)) sys.stdout.write(f"{res}\n") sys.exit(0) # 找到一組解就中止程式 return for i in range(start, tot+1): class_idx = (i-1)//r if class_cnt[class_idx] >= 2 or used_skill[skills[i]]: continue class_cnt[class_idx] += 1 used_skill[skills[i]] = True path.append(i) dfs(i+1, path, used_skill, class_cnt) class_cnt[class_idx] -= 1 used_skill[skills[i]] = False path.pop() dfs(1, [], [False]*(n+1), [0]*m) ``` <br /> 不使用 sys.exit(0) 中止程式，費時最久約為 0.9 s，使用記憶體最多約為 3 MB，通過測試。 ```python= def solve(): import sys sys.setrecursionlimit(10000) data = sys.stdin.read().split() ptr = 0 n, m, r, k, t = map(int, data[ptr:ptr+5]) ptr += 5 tot = m*r skills = [0] + list(map(int, data[ptr:ptr+tot])) ptr += tot cnt = [0] def dfs(start, path, used_skill, class_cnt, stop): if stop: return True if len(path) == k: cnt[0] += 1 if cnt[0] == t: res = " ".join(map(str, path)) sys.stdout.write(f"{res}\n") return True return False for i in range(start, tot+1): class_idx = (i-1)//r if class_cnt[class_idx] >= 2 or used_skill[skills[i]]: continue class_cnt[class_idx] += 1 used_skill[skills[i]] = True path.append(i) # 如果下層回傳 True，已經找到解，回傳 True if dfs(i+1, path, used_skill, class_cnt, stop): return True class_cnt[class_idx] -= 1 used_skill[skills[i]] = False path.pop() return False # 這個分枝沒有找到解 dfs(1, [], [False]*(n+1), [0]*m, False ) if __name__ == "__main__": solve() ``` <br /><br /> ## C++ 程式碼 以下的程式還有改進的空間。如果沒有第20行的 **exit(0);** 費時最久約為 52 ms，使用記憶體最多約為 312 kB，通過測試；如果加上這行，找到一組解就中止程式，費時最久約為 47 ms，使用記憶體最多約為 308 kB，通過測試。 ```cpp= #include <cstdio> #include <cstdlib> // for exit(0); #include <vector> #include <map> using namespace std; int n, m, r, k, t, tot, cnt; vector<int> skills, class_cnt; map<int, bool> used_skill; void dfs(int start, vector<int>& path) { if ((int)path.size() == k) { cnt++; if (cnt == t) { for(int i=0; i<k; i++) { printf("%d", path[i]); if (i == k-1) printf("\n"); else printf(" "); } exit(0); // 找到一組解就中止程式，需要引入 cstdlib } return; } for(int i=start; i<=tot; i++) { int class_idx = (i-1) / r; if (class_cnt[class_idx] >= 2 || used_skill[skills[i]]) { continue; } class_cnt[class_idx]++; used_skill[skills[i]] = true; path.push_back(i); dfs(i+1, path); class_cnt[class_idx]--; used_skill[skills[i]] = false; path.pop_back(); } } int main() { scanf("%d %d %d %d %d", &n, &m, &r, &k, &t); tot = m*r; cnt = 0; skills.resize(tot + 1); class_cnt.assign(m, 0); used_skill.clear(); for(int i=1; i<=tot; i++) { scanf("%d", &skills[i]); } vector<int> path; dfs(1, path); return 0; } ``` <br /> 不使用 cstdlib 函式庫的 exit(0)，改用回傳 bool 值的方式在找到一組解就停止程式，費時最久約為 43 ms，使用記憶體最多約為 312 kB，通過測試。 ```cpp= #include <cstdio> #include <vector> #include <map> using namespace std; int n, m, r, k, t, tot, cnt; vector<int> skills, class_cnt; map<int, bool> used_skill; bool dfs(int start, vector<int>& path, bool stop) { if (stop) return true; // 已經找到解 if ((int)path.size() == k) { cnt++; if (cnt == t) { for(int i=0; i<k; i++) { printf("%d", path[i]); if (i == k-1) printf("\n"); else printf(" "); } return true; } return false; } for(int i=start; i<=tot; i++) { int class_idx = (i-1) / r; if (class_cnt[class_idx] >= 2 || used_skill[skills[i]]) { continue; } class_cnt[class_idx]++; used_skill[skills[i]] = true; path.push_back(i); // 如果下層有找到解，回傳 true if (dfs(i+1, path, stop)) { return true; } class_cnt[class_idx]--; used_skill[skills[i]] = false; path.pop_back(); } return false; // 這個分枝沒有找到解，回傳 false } int main() { scanf("%d %d %d %d %d", &n, &m, &r, &k, &t); tot = m*r; cnt = 0; skills.resize(tot + 1); class_cnt.assign(m, 0); used_skill.clear(); for(int i=1; i<=tot; i++) { scanf("%d", &skills[i]); } vector<int> path; bool stop = false; dfs(1, path, stop); return 0; } ``` <br /> --- ###### tags:`APCS`、`Python`、`C++`