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,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

题意:给出n和m,然后有很多个集合{1,2,,,,n}的非空子集,按照一定方式排列,例如n==3时,

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

然后输出第m个序列。

结题思路,仔细观察可以看出,1、2、3开头的集合个数是一样多的,因此那m/(每组个数)可以得出第一个数字,然后依次类推即可

#include<cstdio>
#include<iostream>
#define LL long long int
using namespace std;
int main(){
    int n,a[21],i;
    LL m,t;
    LL p[21]={0,1};
    for(i=2;i<=20;i++){
        p[i]=p[i-1]*(i-1)+1;//0、1、2、5、16
    }
    while(cin>>n>>m){
        for(i=0;i<=20;i++)
            a[i]=i;
        while(n--&&m){
            t=m/p[n+1]+((m%p[n+1])?1:0);
            cout<<a[t];//当前的首数字
            for(i=t;i<=n;i++)
                a[i]=a[i+1];//回到n-1个数字,更新输出数组
            m-=((t-1)*p[i]+1);//去掉前面的小于t开头的组合,且将去掉一个仅有t的集合
            printf(m==0?"\n":" ");
        }
    }
    return 0;
}
时间: 2024-10-30 01:55:32

hdu 2062 Subset sequence【有点康拓展开的意思】的相关文章

hdu 2454 Degree Sequence of Graph G

点击打开链接 Degree Sequence of Graph G Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1997    Accepted Submission(s): 850 Problem Description Wang Haiyang is a strong and optimistic Chinese youngst

hdu 5400 Arithmetic Sequence

click here~~ ***Arithmetic Sequence*** Problem Description A sequence b1,b2,⋯,bn are called (d1,d2)-arithmetic sequence if and only if there exist i(1≤i≤n) such that for every j(1≤j<i),bj+1=bj+d1 and for every j(i≤j<n),bj+1=bj+d2. Teacher Mai has a

hdu 1711 Number Sequence

点击打开链接hdu1711 思路:KMP kmp算法: 1 kmp是用来匹配字符串,只能够匹配单一的字符串 2 kmp的算法的过程:   1:假设文本串的长度为n,模式串的长度为m:   2:先例用O(m)的时间去预处理next数组,next数组的意思指的是当前的字符串匹配失败后要转到的下一个状态:   3:利用o(n)的时间去完成匹配: 3 时间复杂度为o(n+m)即o(n): 代码: #include<algorithm> #include<iostream> #include

杭电ACM 2000-&amp;gt;2099 100道题 详细解题报告出炉

我去年暑假花了5天,把杭电ACM网站上2000到2099这100道题全AC了,又花了10来天精心写解题报告.里面包括题目.解题思路.编程技巧以及参考源码.所有代码都是使用C/C++写的. 最近整理资料时无意间发现,打包成chm文件和大家分享.我已经上传到CSDN上了.下载地址:http://download.csdn.net/source/492194 也可到我的Google Sites上下载. 题号 题名 题号 题名 2000 ASCII码排序 2001 计算两点间的距离 2002 计算球体积

KMP专题【完结】

第一题 hdu 1711 Number Sequence 点击打开hdu 1711 思路: 1 kmp是用来匹配字符串,只能够匹配单一的字符串 2 kmp的算法的过程:   1:假设文本串的长度为n,模式串的长度为m:   2:先例用O(m)的时间去预处理next数组,next数组的意思指的是当前的字符串匹配失败后要转到的下一个状态:   3:利用o(n)的时间去完成匹配: 3 时间复杂度为o(n+m)即o(n): 点击查看代码 第二题 hdu 1686 oulipo 点击打开hdu 1686

hdu 5504 GT and sequence【BestCoder Round #60 】

GT and sequence Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1441    Accepted Submission(s): 336 Problem Description You are given a sequence of N integers. You should choose some numbers(at

HDU 3038 How Many Answers Are Wrong? :带权并查集

链接: http://acm.hdu.edu.cn/showproblem.php?pid=3038 题目: Problem Description TT and FF are ... friends. Uh... very very good friends -________-b FF is a bad boy, he is always wooing TT to play the following game with him. This is a very humdrum game. T

HDU 2489 Minimal Ratio Tree (DFS枚举+最小生成树Prim)

链接: HDU : http://acm.hdu.edu.cn/showproblem.php?pid=2489 POJ  : http://poj.org/problem?id=3925 题目: Problem Description For a tree, which nodes and edges are all weighted, the ratio of it is calculated according to the following equation. Given a comp

HDU 3461:Code Lock(并查集+二分求幂)

链接: http://acm.hdu.edu.cn/showproblem.php?pid=3461 原题: Problem Description A lock you use has a code system to be opened instead of a key. The lock contains a sequence of wheels. Each wheel has the 26 letters of the English alphabet 'a' through 'z',