首页 > 代码库 > P2727 Stringsobits

P2727 Stringsobits

   01串 Stringsobits

题目背景

考虑排好序的N(N<=31)位二进制数。

题目描述

他们是排列好的,而且包含所有长度为N且这个二进制数中1的位数的个数小于等于L(L<=N)的数。

你的任务是输出第i(1<=i<=长度为N的二进制数的个数)小的(注:题目这里表述不清,实际是,从最小的往大的数,数到第i个符合条件的,这个意思),长度为N,且1的位数的个数小于等于L的那个二进制数。

(例:100101中,N=6,含有位数为1的个数为3)。

输入输出格式

输入格式:

 

共一行,用空格分开的三个整数N,L,i。

 

输出格式:

 

共一行,输出满足条件的第i小的二进制数。

 

输入输出样例

输入样例#1:
5 3 19
输出样例#1:
10011

说明

题目翻译来自NOCOW。

USACO Training Section 3.2

思路:

注意点:“第几小的数”用int不够,要用long long int。

我们的目标是找到第i个长为N的,最多含有L个1的二进制数。那么,用F[k, i]来表示在前k位中,恰有i个1的二进制数的数量。Sum(F[k, 0~i])就表示在前k位中,最多有i个1的二进制数的数量。

转移方程很好写,边界条件是F[k, 0] = 1(在前k位中,没有1的二进制数只有一个,每一位都是0)。

F[k, i] = F[k-1, i] + F[k-1, i-1],分别是第k位是0和第k位是1。

接下来,for k in [0, n](注意,从0开始循环),求出Sum(F[k, 0~L])。如果这个和大于等于p,就说明我们要求的这个数字包含在bit[k]=1的情况里。那么我们就可以把p扣除掉bit[k]=0的情况,也就是扣掉Sum(F[k-1, 0~i])【即第k位是0时,至多有i个1的二进制数的数量。】。

确定了bit[k]=1,那么就可以把L和n各扣掉1,继续找下一个为1的位了(重复上面步骤)。

最后倒序输出这个二进制数就完成了。

代码:

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<string.h>
 5 #include<math.h>
 6 #include<stdlib.h>
 7 #include<ctype.h>
 8 #include<stack>
 9 #include<queue>
10 #include<map>
11 #include<set>
12 #include<vector>
13 #define ll long long
14 #define  db double
15 using namespace std;
16 const int N=1e6+5;
17 const int mod=1e9+7;
18 int dp[33][33];
19 bool num[33];
20 void search(int n, int l, long long int p) {
21     long long int s, last;
22     for (int k = 0; k <= n; k++) {
23         last = s;
24         s = 0;
25         for (int i = 0; i <= l; i++) {
26             s += dp[k][i];
27         }
28         if (s >= p) {
29             num[k] = true;
30             return search(n-1, l-1, p-last);
31         }
32     }
33 }
34 int main() {
35     int n, l;
36     long long int p;
37     scanf("%d %d %lld", &n, &l, &p);
38     for (int k = 0; k <= n; k++) {
39         dp[k][0] = 1;
40     }
41     for (int k = 1; k <= n; k++) {
42         for (int i = 1; i <= k; i++) {
43             dp[k][i] = dp[k-1][i] + dp[k-1][i-1];
44         }
45     }
46     search(n, l, p);
47     for (int k = n; k >= 1; k--) {
48         printf("%d", num[k]);
49     }
50     return 0;
51 }

 

P2727 Stringsobits