HDU杭电acm2062-Subset sequence

题目地址：  http://acm.hdu.edu.cn/showPRoblem.php?pid=2062

/************************************************************************

本想用深搜（dfs），不过超时了。。无奈绞尽脑汁，用了种无奈的方法。

/********************

把他的子集画成一个多叉树的图，假设图中红线圈起来的这一路就是答案，如果用遍历树的方法找到这个答案，必定超时。

那么就及早的剪枝，不符合条件的答案，直接不往下探索了，

/*********************

其实每一个结点就代表一个子集，子集就是答案。上图假设红色圆圈的结点就是答案，答案就是这一整条路连起来的数字。

每往下走一个结点，都筛选出正确的唯一一条分支。

/****************************************************************

代码如下：

/********************

#include<stdio.h>#include<algorithm>using namespace std;long long c[21]={0,1},j,n; //j用来统计当前走到哪里了int m;void swap(int &a,int &b)//c++中的引用，实现值得交换{    int temp=a;    a=b;    b=temp;}void po(int a[],int begen){    if(j>=n||begen>m)    {        printf("%d",a[1]);        for(int i=2;i<begen;i++)            printf(" %d",a[i]);        puts("");        return;    }    long long t=j;//用t暂时记录下j    for(int i=begen;i<=m;i++)    {        if(i-begen+1==(n-t-1)/(c[m-begen]+1)+1)//判断条件很复杂,意思是检索到有答案的那一个分支时，就执行下面        {            j++;   //printf("树的路径:**%3d ** i:%3d,begen:%3d** /n",i-begen+1,i,begen);            swap(a[i],a[begen]);        //选择a[i]这个数字，把它交换到第begen的位置            sort(a+begen+1,a+m+1);    //对剩下的数字排序（字典序，从小到大）            po(a,begen+1);      //递归，寻找下一个数字，排到（数组a中）begen+1的位置            break;//以后的路都不符合了，直接break；        }        else            j+=c[m-begen]+1;//统计走到第多少个子集了    }}int main(){    int a[21]={0,1};    for(long long i=2;i<=20;i++)        c[i]=i*(c[i-1]+1);    while(~scanf("%d%lld",&m,&n))    {        for(int i=1;i<=m;i++)            a[i]=i;        j=0;        po(a,1);    }    return 0;}