Stringsobits

---

[描述

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

你会发现，这很有趣。因为他们是排列好的，而且包含所有可能的长度为N且含有1的个数小于等于L(L<=N)的数。

你的任务是输出第I（1<=I<=长度为N的二进制数的个数）大的，长度为N，且含有1的个数小于等于L的那个二进制数。

格式

PROGRAM NAME: kimbits

INPUT FORMAT:

(file kimbits.in)

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

OUTPUT FORMAT:

(file kimbits.out)

共一行，输出满足条件的第I大的二进制数。

SAMPLE INPUT

5  3  19

SAMPLE OUTPUT

10011

 

分析：

这道题算比较经典的DP+构造了吧~~~

 

一开始想着暴力判断 O(logN*N)，枚举N*判断每一个数1的个数logN。这种显然超时的算法下次就不要想了= =！。。。（每次想好前先给我算一下复杂度！）

 

然后就考虑DP吧~~~

 

先用动态规划计算：长度为I的01串，1的个数不大于j的有多少个

其状态表示为f[i,j]

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

边界：f[i,0]=1,f[0,i]=1;

然后就是用字符串构造了(注：这里的K就是原题中的I)

第一次，寻找1的最高位位置，从次高位开始扫描(i:=n-1 downto 1)，看从当前位到最后，1的个数是否超过L，比较f[i,l]与K的大小。如果f[i,l]>=K这一位不为1(因为满足条

件的前K个都是由后面i-1位01串构成的)，向S加入一个‘0’补足高位；否则，找到了第一个f[i,l]<k(也就是说，仅由当前i位已经无法构成足至少k个满足条件的01串)，这是

第i+1位必须添上一个‘1’，然后dec(k,f[i,l]),dec(l)

然后按照相同的方法继续构造接下来的‘1’，不足的全部由‘0’补足 

 

PS:这个算法标准化应该就是康托展开 吧~~~O.O。。。

 

代码：

1 /* 2 ID:138_3531 3 LANG:C++ 4 TASK:kimbits 5 */ 6  7  8 #include 
     
       9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 #include 
           
            15 #include 
            
             16 #include 
             
              17 #include 
              
               18 #include