本蒟蒻又双叒叕被爆踩辣！
其实只要理解了就会觉得这是个***题！
这题给的标签是 dp，搜索，数论
但是可以用二分的思路做！
Solution：
从最高位开始枚举，
我们考虑每一位，是不是只可以取0/1
那么我们就先求出当此位置为0时，它可以做到的方案数（等会再告诉你们为什么要求
我们想一想，什么时候此位该为0，什么时候此位该为1？？？
我们求出它的方案数，那这个方案数是不是就是但此位为0时可以达到的最大值；
如果i比这个最大值还要大的话，此位为0是不是就做不到了。
result：
所以，如果这个方案数比i大，说明排名为i的数一定属于最高位是0的数，否则就属于最高位为1的数。
你就逐位考虑下来就可以了！
这就是运用了二分的思路，对其进行求解。
至于方案数的话，在最开始跑一遍dp就行了，
g[i][j] = g[i - 1][j - 1] + g[i - 1][j];
就是它为0/1前一位的值相加即可。
code：
#include<bits/stdc++.h>//万能头
using namespace std;
#define maxn 60//可以稍微大一点
#define int long long//这是个坑
#define Rep(x, a, b) for(int x = a; x <= b; ++ x)
#define Dep(x, a, b) for(int x = a; x >= b; -- x)
int n, l, k, g[maxn][maxn], sum[maxn][maxn], a[maxn];
//g[k][i]是来表示在前k位中，恰有i个1的二进制数的数量
//sum[k][i]是来表示在前k位中，最多有i个1的二进制数的数量
//a[i]是当前这一位是0/1，输出是用。
void dfs(int x, int l, int k){
if(x == 0){//跑到了最后一位了
Dep(i, n, 1){//输出路径
printf("%d", a[i]);
}
exit(0);//不可以用return，return只结束当前这一轮函数，exit(0)就可以直接结束程序。
}
if(k <= sum[x - 1][l]){//如果它小于或等于此位取0时的最大值
a[x] = 0;//当前这位就取0；
dfs(x - 1, l, k);//并且直接跑到下一位
}
else{//如果它大于的话
a[x] = 1;//当前就取1；
dfs(x - 1, l - 1, k - sum[x - 1][l]);//并且跑下一位的时候要把还可以取的‘1’的数量-1，然后要跑的数位也会减去这位取了‘1’以后减下的值。
}
}
signed main(){
scanf("%d%d%d", &n, &l, &k);//RT
g[0][0] = 1;//初始化，一定要记得
Rep(i, 1, n){
g[i][0] = 1;//如果只要0个‘1’，肯定只有1种方法。
Rep(j, 1, n){
g[i][j] = g[i - 1][j - 1] + g[i - 1][j];//递归求恰有i个1的二进制数的数量
}
}
Rep(i, 0, n){
Rep(j, 0, n){
Rep(k, 0, j){
sum[i][j] += g[i][k];//跑一下求最多有i个1的二进制数的数量
}
}
}
dfs(n, l, k);//搜索一下就可以了
return 0;
}
在这里还说一下我前两次Wa在那
First：
我求sum[ ][ ]的时候，不是从第0位开始跑的。。。
Second：
没开long longQAQ
Ps：请看懂再抄
京公网安备 11010502036488号