题目链接（洛谷）
题目大意
考虑排好序的\(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;
}
|