免费的网站建设有哪些,网站关键词工具有哪些,手机主页,网站浮动窗口怎么做题目再现
题目内容#xff1a;
给定N个数字#xff0c;再从中选定M个数字出来。
将每一种组合内的数字由小到大排列之后#xff0c;
将所有组合按照字典序排列#xff0c;
请你找出第X组的第Y个数字。
给定的数字为1~N。
范例1 (N,M,X,Y) (5,2,8,2)
所有组合按顺序排列为…
题目再现
题目内容
给定N个数字再从中选定M个数字出来。
将每一种组合内的数字由小到大排列之后
将所有组合按照字典序排列
请你找出第X组的第Y个数字。
给定的数字为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个数字为4。输入格式:
第一行有一个数字T代表有多少组测资。
每一组测资有一行
第一行四个数字N、M、X、Y
意义如题目所述。
测资范围
T 1000
1 N 12
1 M N
0 X C(N, M)
0 Y N输出格式
对于每一笔测资找出第X组第Y个数字。
将所有测资的答案加总后再输出。输入样例
2
5 2 8 2
6 3 7 3输出样例
10
时间限制500ms内存限制32000kb算法实现
这个题可以通过DFS获取所有的序列通过box数组记录序列信息在获取序列的时候使用计数器判断需要找的位置。
#include stdio.h
#include string.hint 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;
} 拓展阅读 小谈深度优先搜索 博客名称王乐平博客 博客地址http://blog.lepingde.com CSDN博客地址http://blog.csdn.net/lecepin
