Stringsobits 解题报告

刚开始想到位运算，Matrix67有说过一个求某个二进制数中1的个数的方法。那么可以直接枚举，然后判断1的个数是否大于L，直到求出符合条件第I个数。但是由于最后结果最大可以到LONG_MAX，所以即使用位运算也会超时。

既然filter不可以，那么考虑generator。

通过打出前几个自然数的二进制：

000000
000001
000010
000011
000100
000101
000110
000111
001000
001001
001010
001011
001100
001101
001110
001111
010000
010001
010010
010011
010100
010101
010110
010111
011000
011001
011010
011011
011100
011101
011110
011111

可以发现，如果用f[i][j]表示长度为i的二进制串恰好含有j个1的串的个数，可以得到如下关系：
f[i][j] = f[i - 1][j] + f[i - 1][j - 1]
f[i][0] = 1
f[i][i] = 1

即可用下列语句递推

1 for(i = 1;i <= N;i ++)
2 {
3     f[i][i] = f[i][0] = 1;
4     for(j = 1;j < i;j ++)
5         f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
6 }

因为题目要求的是1的个数不大于L的串，因此把f[i][j]转换为长度为i的串出现1的次数小于j的个数

1 for(i = 1;i <= N;i ++)
2     for(j = 1;j <= N;j ++)
3         f[i][j] += f[i][j - 1];

现在所需要做的就是构造出答案二进制串，我在这个问题上卡了很久。

C语言: 高亮代码由发芽网提供

01 for(i = N;i > 0;i --)  //从高位向低位推
02 {
03     if(f[i - 1][L] < I) //此处不能使用<=，我就是在这里纠结好久的，为什么可以观察上面的二进制串
04     {
05         printf("1");
06         I -= f[i - 1][L];
07         L --;  //既然该位有了一个1，剩下的位置的1的个数的上限就要-1
08     }
09     else printf("0");
10 }

全部代码：

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03
04 long long N,L,I;  //注意使用long long型，否则第10个数据过不了
05 unsigned long long f[32][32];
06
07 void solve()
08 {
09     int i,j;
10     for(i = 0;i <= N;i ++)  //这个是上面代码所没有的，应该也算递归边界吧，其实也是为重构二进制串做边界
11         f[0][i] = 1;
12     for(i = 1;i <= N;i ++)
13     {
14         f[i][i] = f[i][0] = 1;
15         for(j = 1;j < i;j ++)
16             f[i][j] = f[i - 1][j - 1] + f[i - 1][j];  //这个其实就是个杨辉三角
17     }
18     for(i = 1;i <= N;i ++)
19         for(j = 1;j <= N;j ++)
20             f[i][j] += f[i][j - 1];
21     for(i = N;i > 0;i --)
22     {
23         if(f[i - 1][L] < I)
24         {
25             printf("1");
26             I -= f[i - 1][L];
27             L --;
28         }
29         else printf("0");
30     }
31     printf("\n");
32     return;
33 }
34
35 int main()
36 {
37     freopen("kimbits.in","r",stdin);
38     freopen("kimbits.out","w",stdout);
39     scanf("%Ld%Ld%Ld",&N,&L,&I);
40     solve();
41     fclose(stdout);
42     fclose(stdin);
43     return 0;
44 }