P1243 排序集合
网页链接
P1243 排序集合
题目描述
对于集合N = { 1 , 2 , ⋯ , n } N=\{1,2,\cdots,n\}N={1,2,⋯,n}的子集，定义一个称之为“小于”的关系：
设S 1 = { X 1 , X 2 , ⋯ , X i } S1=\{X_1,X_2,\cdots,X_i\}S1={X1,X2,⋯,Xi}，( X 1 < X 2 < ⋯ < X i ) (X_1<X_2<\cdots<X_i)(X1<X2<⋯<Xi)，S 2 = { Y 1 , Y 2 , ⋯ , Y j } S2=\{Y_1,Y_2,\cdots,Y_j\}S2={Y1,Y2,⋯,Yj}，( Y 1 < Y 2 < ⋯ < Y j ) (Y_1<Y_2<\cdots<Y_j)(Y1<Y2<⋯<Yj)，如果存在一个k kk，( 0 ≤ k ≤ min ( i , j ) ) (0\leq k\leq\min(i,j))(0≤k≤min(i,j))，使得X 1 = Y 1 , ⋯ , X k = Y k X_1=Y_1,\cdots,X_k=Y_kX1=Y1,⋯,Xk=Yk，且k = i k=ik=i或X k + 1 < Y k + 1 X_{k+1}<Y_{k+1}Xk+1<Yk+1，则称S 1 S1S1“小于”S 2 S2S2。
你的任务是，对于任意的n ( n ≤ 31 ) n(n\leq31)n(n≤31)及k ( k < 2 n ) k(k<2^n)k(k<2n)，求出第k kk小的子集。
输入格式
输入文件仅一行，包含两个用空格隔开的自然数，n nn和k kk。
输出格式
输出文件仅一行，使该子集的元素，由小到大排列。空集输出0 00。
输入输出样例 #1
输入 #1
3 4输出 #1
1 2 3解题思路
本题核心是子集字典序映射 + 二进制计数，将抽象的子集排序问题转化为简单的数值计算。题目定义的子集“小于”关系等价于字典序排序，空集为第1小的子集。总子集数为2 n 2^n2n，利用二进制规则遍历数字1 ∼ n 1 \sim n1∼n：对每个数i ii，计算其后方可组成的子集总数2 n − i 2^{n-i}2n−i，若剩余排名k kk小于等于该值，则i ii属于目标子集；否则减去该总数并跳过。特判空集（k = 1 k=1k=1）输出0 00，其余按规则筛选元素后输出。算法时间复杂度O ( n ) O(n)O(n)，简洁高效，完美适配n ≤ 31 n \le 31n≤31的数据范围。
总结
核心逻辑：子集字典序排序等价于二进制计数，逐位判断数字是否属于目标子集。
关键操作：空集特判、按序遍历数字、幂次计算筛选结果。
效率保障：线性遍历无冗余计算，精准匹配题目排序规则，无超时风险。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,k;scanf("%lld%lld",&n,&k);if(k==1){printf("0\n");return0;}k--;for(ll i=1;i<=n;i++){if(k==0)break;if(k<=pow(2,n-i)){printf("%lld ",i);k--;}else{k-=pow(2,n-i);}}return0;}
