题解 P1243 【排序集合】

lytqwq · 2019-11-22 22:47:38 · 题解

说炸int为什么不好好看题呢

对于N的子集，每个数我们都可以取或者不取，

如果不取1，会有2^(n-1)种方法在“不取1时”的前面，

就是有2^(n-1)种方法比“不取1时”小，

所以当k>2^(n-1)时，不取第一个数，

k-=pow(2,n-i)，再考虑取不取2，我们发现：

如果不取i，会多2^（n-i）种方法比“不取i时” 小

所以，当k<=2^（n-i）时，我们只能取i，因为如果不取就会多2^（n-i）种方法比不取i时小

但这时我们要k - - ,因为还有一种就是不取i且之后所有都不取的情况。

然后k<2^n的，所以并不会炸int，上代码：

#include<bits/stdc++.h>
using namespace std;
int n,k;
int main()
{
    scanf("%d%d",&n,&k);
    if(k==1)
    {
        printf("0\n");
        return 0;
    }
    k--;
    for(int i=1;i<=n;i++)
    {
        if(k==0)
        {
            break;
        }
        if(k<=pow(2,n-i))
        {
            printf("%d ",i);
            k--;
        }
        else
        {
            k-=pow(2,n-i);
        }

    }

}