---

題目再現(xiàn)

題目內(nèi)容： 給定N個數(shù)字，再從中選定M個數(shù)字出來。 將每一種組合內(nèi)的數(shù)字由小到大排列之后， 將所有組合按照字典序排列， 請你找出第X組的第Y個數(shù)字。 給定的數(shù)字為1~N。 范例1 (N,M,X,Y) = (5,2,8,2) 所有組合按順序排列為：(1 2), (1 3), (1 4), (1 5), (2 3),(2 4), (2 5), (3 4), (3 5), (4 5) 所以第8組第2個數(shù)字為4。輸入格式: 第一行有一個數(shù)字T代表有多少組測資。 每一組測資有一行， 第一行四個數(shù)字N、M、X、Y， 意義如題目所述。 測資范圍： T < 1000 1 < N < 12 1 < M < N 0 < X <= C(N, M) 0 < Y <= N輸出格式： 對于每一筆測資，找出第X組第Y個數(shù)字。 將所有測資的答案加總后再輸出。輸入樣例： 2 5 2 8 2 6 3 7 3輸出樣例： 10 時間限制：500ms內(nèi)存限制：32000kb

---

算法實現(xiàn)

這個題可以通過DFS獲取所有的序列，通過box數(shù)組記錄序列信息，在獲取序列的時候使用計數(shù)器判斷需要找的位置。

#include <stdio.h> #include <string.h>int book[12], box[12]; int times; long long sum = 0;void dfs(int step, int n, int m, int x, int y){int i;if(step >= m){times ++;if(times == x){sum += box[y - 1];}return;}for(i = 1; i <= n; i ++){if(book[i - 1] == 0){if(step >= 1 && box[step - 1] > i){continue;}box[step] = i;book[i - 1] = 1;dfs(step + 1, n, m, x, y);book[i - 1] = 0;}} }int main(){int T;int N, M, X, Y;scanf("%d", &T);while(T --){memset(book, 0, sizeof(book));times = 0;scanf("%d %d %d %d", &N, &M, &X, &Y);dfs(0, N, M, X, Y);}printf("%lld", sum);return 0; }

---

拓展閱讀

小談深度優(yōu)先搜索

---

博客名稱：王樂平博客

博客地址：http://blog.lepingde.com

CSDN博客地址：http://blog.csdn.net/lecepin

總結

以上是生活随笔為你收集整理的Lotto（DFS处理）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。