USACO/kimbits

来自NOCOW

[编辑] 分析

[编辑] 官方题解

假设我们知道如何计算含有给定个数的二进制0和1的集合大小。也就是说，假设我们有一个函数sizeofset(n,m)返回含有至多m个1的n位二进制数的集合大小。

然后我们可以如下解决这个问题，我们在寻找至多m个1的n位二进制数的集合的第i个元素。这个集合有两部分，开始于0的和开始于1的。有sizeofset(n-1, m)个数以0开始且至多有m个'1',有sizeofset(n-1,m-1)个数以1开始并且至多有m-1个'1'。

所以如果这个序号(i)比sizeofset(n-1,m)小，题目所求的数出现在开始于0的那部分，不然的话，它以一个'1'开始。

由"printbits"实现的递归算法很合适

所剩的唯一困难是计算"sizeofset",我们可以用上面描述的特征使用动态规划解决这个问题。 sizeofset(n, m) = sizeofset(n-1, m) + sizeofset(n-1, m-1)

并且对于所有m,sizeofset(0, m) = 1.我们使用double来存储大小，但这矫枉过正了，因为重写的问题只要求31位而不是32位。

[编辑] 注意

此题虽简单，但有一个坑：最大的I可达到2147483648，超出32bit signed int范围！大家要谨防被坑。。。（从坑里刚爬出来的某人如是说）

同意，此坑毫无意义，差评！

同意，刚好大1，神坑，差评！

同意，深坑，不玩了，差评！

[编辑] 动态规划

设长度为j的01串，1的个数不大于k的个数为f[j,k]

方程：f[j,k]=f[j-1,k]+f[j-1,k-1]; //分别表示在当前位加上0和加上1时的两种状况

边界：f[j,0]=1,f[0,j]=1;f[j,k](k>j)=f[j,j]

这样我们得到了所有的f[j,k](j,k∈Z, j,k>0),需要做的就是据此构造出所求字符串.

设所求串为S,假设S的位中最高位的1在自右向左第K+1位，那么必然满足F[K,L]< I,F[K+1,L] >=I,这样的K是唯一的。所以S的第一个1在从右至左第K+1位.因为有F[K,L]个串第K+1位上为0，所以所求的第I个数的后K位就应该是满足"位数为K且串中1不超过L-1个"这个条件的第I-F[K,L]个数。

于是我们得到这样的算法:

for K:=n-1 downto 0 do //题目保证有解，所以f[N,L]>I
  if F[K,L]<I then
  begin
    s[N-K]:='1';
    dec(I,F[K,L]);{第K+1位是1，所以I减去第K+1位是0的串的个数}
    dec(L);
  end;
//注意I可能为2147483648th element ,所以用无符号整形存储I。F在F[32][32]为2147483648。所以F要用int64。

注(C++)：
d[i][j]表示长度为i，1的个数至多为j的二进制数量
边界：d[i][0]=1;(任何位没有至多0个1的情况只有一种0000000....)d[0][i]=1;(主要是为了在递推的过程中,长度为1,1个数至多j的二进制转移正确。（长度为1的情况下，只有0,1两种）)
d[i][j]=d[i-1][j]+d[i-1][j-1]分别有第i位为1，0两种情况。//前者是第i位为0的情况下，后者为第i位为1的情况
打印解得原理：
有转移方程可以知道，I>d[i-1][L]的情况时候，必定存在d[i-1][j-1]的情况，此时我们确定第i位必定为1，所以减去第i位为0,长度为i的情况 剩下的就是第i位为1的情况 

比如找3位，1个数不超过3个，的第7个二进制 数 
000
001
010
011
减掉上面的 ，第三位为0的情况 剩下的是： 
100
101
110
111
减去的上面部分  7-4=3；剩下4种第3位为1的情况，则下面讨论的其实是： 
00
01
10
11
转移到这了 重复这样的步骤（求2位，1个数不超过3-1=2个，第3位二进制数），就能确定第2位第1位了  
————————————————————————————————————————————来自一名想了一天没看懂，第二天终于看懂的蒟蒻的想法..补充..

[编辑] 优化

其实从基本的组合原理出发，我们可以推出F[j,k]的表达式:F[j,k]=C[j,0]+C[j,1]+C[j,2]+...+C[j,k].这里C[i,j]表示从i个元素中取j的组合数因为C[m,n]=C[m-1,n-1]+C[m-1,n],可得

F[j,k]=C[j-1,0]+C[j-1,0]+C[j-1,1]+...+C[j-1,K]+C[j-1,k-1]+C[j-1,K]

=2*(C[j-1,0]+C[j-1,1]+...+C[j-1,k-1])+C[j-1,K]

=2*F[j-1,k-1]+C[j-1,k]

这样我们就可以用一个递归程序求解该问题.

用 $F[j-1,k-1]=\frac{(F[j,k]-C[j-1,k])}{2}$ ,我们首先可以仅用O(N)的时间就可以计算出F(j,L)的值,并记录C(j,L).若需添"1",则可由上式计算出F(J-1,L-1)的值,并用O(1)的时间将C(J,L)改进为C(J-1,L-1);若只需添"0",则可先计算出C(J-1,L)的值,再将F(J,L)改进为F(J-1,L),也是O(1)的时间. 因此我们只需要保留C,F,N,M,K,I等少量临时变量,空间复杂度为常数级,且可以在O(N)的时间内计算出解,非常优化.

(还有C[I,J]与C[I-1,J],C[I,J-1]之间的O(1)改进方法,参见程序3,自己推也很容易)

(这是LF大牛提出的方法,并通过了USACO的数据,参见PASCAL程序3)

[编辑] 搜索+剪枝

如果暴搜的话，第十个点就会超时。

这里要小小地加上一个位运算里的剪枝（假设i从0开始递增，符合条件的话temp+1）：

p为i当前的1的个数，则!(i&((1LL<<(n-p))-1))为真的话，就是i后边连续的0个数大于等于p，然后在判断一下

(temp+(1LL<<(n-p))<k)

如果为true，则i和temp都加上(1LL<<(n-p))，否则结果就是i+k-temp-1，转化成二进制后输出就行了。

效率还算可以，最后三个点都是0.00s过了，最慢的是0.055。

不过要会用Matrix67的分治法求1的个数，然后明白那个剪枝还要有一点位运算的基础

详细见echooat1的C++程序

[编辑] 剪枝2

若 p>N 则可以跳过所有与i最后一个1之前相等的数,因为其p都是大于N的。找最后一个1可用i&(i^(i-1)) （见M67）。即：

  i+=(i&(i^(i-1)))-1;

加上上面的剪枝最慢的一个点 0.027 s,其它全部0.00s。详见skyxxzc1的代码。

[编辑] （高效方法）直接计算组合数，快速缩小搜索范围

     ------消逝者-------

和二分有些类似。。。

首先分段：(xxx代表前面若干个0）
xxxxx0
xxxxx1
----前面这两个可以单独处理----
xxxx10
xxx100
xx1000  //比如搜到在这一段内，子问题就是1000。
x10000
100000

通过计算组合数C[1后面的位数][K]((0<=K<=剩余可用1的个数)&&(K<=1后面的位数))可以直接得出每一段所包含的组合数总和。然后重上到下（见上面分段图）每段依次加起来，确定在某一段范围内后，更新I=I-累加到前面一段的个数，缩小范围，用到1的话把剩余可用1的数量减一，就是变成一个新的子问题，再递归同样处理子问题即可。组合数可以提前计算，计算方法取对数化简变连加即可，这里为了加速又因为表很小，直接打表。详情见C++代码

楼上好大一张表。。

先求出n bit的数含有'1'个数为L的个数（和杨辉三角差一点）

        L : 1 | 2 | 3 | 4 | 5 | ...
     1 bit: 2 | 0 | 0 | ...
     2 bit: 1 | 1 | 0 | ...
     3 bit: 1 | 2 | 1 | ...
     ...

然后再求出前n bit的数含有'1'个数不大于L的个数（先自上到下再从左到右叠加）

        L : 1 | 2 | 3 | 4 | 5 | ...
     1 bit: 2 | 2 | 2 | 2 | ...
     2 bit: 3 | 4 | 4 | 4 | ...
     3 bit: 4 | 7 | 8 | 8 | ...
     4 bit: 5 | 11 | ...
     ...

有了这个表再递归查询时间复杂度为O(NlogI)..

[编辑] 找规律

列出以下的规律，你会发现很有规律

二进制数大小 —— 含有1的位数

1-1 —— 1

2-3 —— 1 2

4-7 —— 1 2 2 3

8-15 —— 1 2 2 3 2 3 3 4

16-31 —— 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5

32-63 —— 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6

很有规律……

[编辑] 规律2

用杨辉三角计算组合数这么二的问题在这里就不说了==！~！下面来发一个一步一步推出解的方法求出C（n,m）n和m都是50，也就是所求出i<=n&&j<=m的所有组合数下面本人来说一个方法

用样例说吧 5 3 19 也就是说先确定第一位

如果第一个是0，也就是说后四个取 1到3 个 long long t = 组合数累加(= _ =)!~! 在这里t是15 最后算出19是大于15的也就是说第一位肯定是1 所以这个序列肯定是序列开头是1的第4个（小学减法）如果是1就把m-- 以此类推……

此方法相当强大全部零秒秒杀

杨辉三角的写法按照我这个

   c[0][0] = 1;
   for(int i = 1; i <= 50; i ++)
   {
       for(int j = 0; j <= 50; j ++)
       {
           c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
       }
   }

零也有用因为最后的时候你是可以选零的我习惯把long long 写成LL (LL大法好)

void solve() {

   for(int i = 1; i <= N; i ++)
   {
       if(L == 0) {cout << "0";continue;}
       LL u = 0;
       for(int j = 0; j <= L; j ++)
       {
           u += c[N - i][j];
       }
       if(I <= u) {cout << "0";}
       else
       {
           cout << "1";
           L --;
           I -= u;
       }
   }
   return;

}

说句话这个东西也可以用在搜索里，就不用什么位运算优化了

by 七哥

[编辑] 参考代码