自动搬运

查看原文

来自洛谷，原作者为

	lytqwq ..

搬运于2025-08-24 21:22:50，当前版本为作者最后更新于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);
		}
		
	}
	
}