HDU 2062 Subset sequence

我是把它当做一道数学题来做的。

这篇题解写的有点啰嗦,但是是我最原始的思维过程。

对于一个集合An= { 1, 2, …, n },在n比较小的情况下,在纸上按字典顺序把所有子集排列一下。

以n=3,m=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

n=3的情况

容易看出前5个打头的是1,紧接着5个子集打头的是2,最后5个开头的是3。

拿前五个来说,除了第一个,后面四个不看开头的1,后面的排列形式和n=2的子集的排列很相似。

f(n)代表集合An所有子集的个数,那么有递推关系:

f(n) = n * (f(n - 1) + 1), f(1) = 1

这里数组taken的作用就是标记某个数是否被占用。

在这个例子里面,要求第一个数,计算(10 - 1) / 5 + 1 = 2。

表示这个数是所有未被占用的数里面从小到大第2个数,也就是2。

再计算一下余数r = (10 - 1) % 5等于4

如果r == 0说明后面的数没有了,跳出循环。

否则m = r;

继续下一轮循环

这里m == 4,计算第二个数 (4 - 1) / 2 + 1 == 2。

现在2已经被第一个数占用了,所以未被占用的第二个数就是3。

后面依次类推。

 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 using namespace std;
 6
 7 int main(void)
 8 {
 9     #ifdef LOCAL
10         freopen("2062in.txt", "r", stdin);
11     #endif
12
13     int n;
14     bool taken[25];
15     int b[25];
16     long long m, a[25];
17     a[1] = 1;
18     for(int i = 2; i <= 20; ++i)
19         a[i] = i * (a[i - 1] + 1);
20
21     while(scanf("%d%I64d", &n, &m) == 2)
22     {
23         memset(taken, false, sizeof(taken));
24         int i;
25         long long r = 1;
26         for(i = 1; i <= n; ++i)
27         {
28             b[i] = ((m - 1) / (a[n - i] + 1)) + 1;
29             int j, k = 0;
30             for(j = 1; j <= n; ++j)
31             {
32                 if(!taken[j])
33                     ++k;
34                 if(k == b[i])
35                     break;
36             }
37             b[i] = j;
38             taken[j] = true;
39             r = (m - 1) % (a[n - i] + 1);
40             if(r == 0)
41                 break;
42             m = r;
43         }
44         for(int j = 1; j < i; ++j)
45             printf("%d ", b[j]);
46         printf("%d\n", b[i]);
47     }
48     return 0;
49 }

代码君

HDU 2062 Subset sequence,布布扣,bubuko.com

时间: 07-11

HDU 2062 Subset sequence的相关文章

hdu(2062)-Subset sequence 组合数学

题意:求集合{1,2,3...n}的第m个排列子集合.集合的大小按字典树排. 例两个元素的排列子集合按字典树排列是:{1},{1,2},{2},{2,1}: 解法:一个一个元素来确定,每次把剩余的元素按大小顺序排列在num中,然后根据排列组合原理直接计算下一个位置的元素的大小,直到排列数为0停止: 代码: /****************************************************** * author:xiefubao **********************

HDU 2062 Subset sequence 数位dp,思路 难度:1

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): 3569    Accepted Submission(s): 1802 Problem Description Consider the aggregate An=

hdu 2062 Subset sequence【有点康拓展开的意思】

Subset sequence Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3441    Accepted Submission(s): 1740 Problem Description Consider the aggregate An= { 1, 2, -, n }. For example, A1={1}, A3={1,2,

2062 Subset sequence

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.

HDU 5014 Number Sequence(2014 ACM/ICPC Asia Regional Xi&#39;an Online) 题解

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5014 Number Sequence Problem Description There is a special number sequence which has n+1 integers. For each number in sequence, we have two rules: ● ai ∈ [0,n] ● ai ≠ aj( i ≠ j ) For sequence a and sequ

hdu 4441 Queue Sequence(splay)

题目链接:hdu 4441 Queue Sequence 这题看了题解写的,题解传送门 1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 #define ls l,m,rt<<1 4 #define rs m+1,r,rt<<1|1 5 using namespace std; 6 typedef long long ll; 7 8 const int N=1e6+7; 9 i

hdu 5297 Y sequence(容斥)

题目链接:hdu 5297 Y sequence 考虑62以内的指数,x为奇数个质数因子,就减掉,偶数个加上.计算x为指数的不满足数直接pow(n,1/x)即可. #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <vector> #include <algorithm> using namespace std; type

KMP算法的定义及KMP练手题 HDU 1711 Number Sequence (我的模板代码)

题意:就是要你来找出b数组在a数组中最先匹配的位置,如果没有则输出-1 思路:直接KMP算法(算法具体思想这位牛写的不错http://blog.csdn.net/v_july_v/article/details/7041827) AC代码: #include<cstdio> #include<cstring> #include<stdlib.h> #include<iostream> using namespace std; #define maxn 100

hdu 5306 Gorgeous Sequence(区间最值更新+求和)

题目链接:hdu 5306 Gorgeous Sequence 题意: 给你一个序列,有三种操作. 0 x y t:将[x,y]的数取min(a[i],t) 1 x y:求[x,y]的最大值 2 x y:求[x,y]的区间和 题解: 吉老师的课件题:传送门 1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;i++) 3 #define ls l,m,rt<<1 4 #define rs m+1,r,rt