本文主要是介绍HDOJ 2062 Subset sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：http://acm.hdu.edu.cn/showproblem.php?pid=2062
题目：
Subset sequence
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2942 Accepted Submission(s): 1540
Problem Description
Consider the aggregate An= { 1, 2, …, n }. For example, A1={1}, A3={1,2,3}. A subset sequence is defined as a array of a non-empty subset. Sort all the subset sequece of An in lexicography order. Your task is to find the m-th one.
Input
The input contains several test cases. Each test case consists of two numbers n and m ( 0< n<= 20, 0< m<= the total number of the subset sequence of An ).
Output
For each test case, you should output the m-th subset sequence of An in one line.
Sample Input
1 1 2 1 2 2 2 3 2 4 3 10
Sample Output
1 1 1 2 2 2 1 2 3 1
解题思路：
找规律，
m = 3, n = 10
1
1 2
1 2 3
1 3
1 3 2
2
2 1
2 1 3
2 3
2 3 1
3
3 1
3 1 2
3 2
3 2 1
我们可以发现f[n] = n * (f[n-1] + 1);f[i]表示有i个元素时，排列的总数序列一共分为n组，每组有(f[n-1] + 1)个元素
思路：求n个元素时序列首元素，序列变为n-1，求n-1个元素时序列首元素......
用t = ceil(m/(f[n-1]+1)),即可求得所求序列在所有序列中是第几组，也就是当前第一个元素在序列数组a中的位置
用数组a表示序列数组[1,2,...,n]（需要动态更新，每次求出t之后，都要删除t位置的元素）
在更新之后，序列数组总长度变为n-1，我们要求一下所求序列的新位置
m = m - (t-1)*(f[n-1]+1) - 1（前面有t-1组，每组f[n-1]个元素）
代码：
#include <cstdio>
#include <cmath>int main()
{int n;long long m, f[25];f[0] = 0;for(int i = 1; i < 21; i++)f[i] = i * (f[i-1] + 1);while(~scanf("%d%I64d", &n, &m)){int first = 1, a[25];for(int i = 1; i <= n; i++)a[i] = i;while(m > 0){int t = ceil(m * 1.0 / (f[n-1] + 1));if(!first) printf(" ");first = 0;printf("%d", a[t]);for(int i = t; i < n; i++)a[i] = a[i+1];m = m - (t - 1) * (f[n-1] + 1) - 1;n--;}puts("");}return 0;
}
这篇关于HDOJ 2062 Subset sequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
