题目链接（洛谷）
题目大意
考虑排好序的$N(1\le N \le 31)$位二进制数，且包含所有长度为$N$且这个二进制数中$1$的个数小于等于$L(l\le N)$的数。
现在输出满足长度为$N$，且$1$的个数小于等于$L$的第$k$小的那个二进制数。
分析
直接搜索全排列产生会超时。考虑$\text{dp}$做法。设$f(i,j)$表示前$i$位中，恰有$j$个$1$的二进制数量。容易得出$f(i,0)=1$， $f(i,j)=f(i-1,j)+f(i-1,j-1),~i$从$0$到$n$。求出在前$i$位中，最多有$j$个$1$的二进制数的数量，即$\sum_{j=0}^L f(i,j)$。如果这个数大于$k$，那么答案的第$i$位为$1$。
实现
$(41ms,~688.00kb)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 50;
ll n, l, k, dp[N][N];
bool ans[N];
void dfs(ll n, ll l, ll k) {
ll sum, lst;
for (int i = 0; i <= n; i++) {
lst = sum, sum = 0;
for (int j = 0; j <= l; j++) {
sum += dp[i][j];
if (sum >= k) {
ans[i] = true;
return dfs(n - 1, l - 1, k - lst);
}
}
}
}
int main() {
cin >> n >> l >> k;
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
}
}
dfs(n, l, k);
for (int i = n; i >= 1; i--) cout << ans[i];
return 0;
}
|