usaco_3_2_2_kimbits_动归统计第k个的未知.cpp

usaco自己做的1到5章的代码

/*
ID: wangyuc2
PROB:kimbits
LANG: C++
*/
/*
这道题又是相隔N久才搞定的！！唉……
其实不是很难，就在于那个动态规划递归方程那边，最开始我是想得用二维数组a[i][j]来记录长度为i的有j个1的序列的个数，后来发现这样做很不方便
后来参考了网上的题解发现，原来递归方程
a[i][j]=a[i-1][j-1]+a[i-1][j] 
边界条件：a[i][0]=1;a[0][i]=1;
这个递归方程中，i是串长，j是串中不超过j个1的个数。
这样写得话，其实就是说，长度为i的串，它的第i位要么是1，要么是零，如果第i位为0，它的个数就等于a[i-1][j]，如果为1，那么它的个数就等于a[i-1][i-1]。
这样计算到串长为i的串中1不超过j个的串的个数a[i][j]，那么从最后一位向前找，就有两种情况：
1.第i位为1，这种情况的话，a[i-1][j]必定要小于I，说明前面i-1位中不超过j个1的数字中不可能找到第I个1的位数不超过j的数字；
2.第i位为0，这种情况下，a[i-1][j]大于等于I，说明前面i-1为中不超过j个1的数字可以构成大于或等于第I个1的位数不超过j的数字。
这样，从最后一位往前找，如果当前位是1，那么num的当前位或一个1，最后把这个二进制串转换成字符串输出就好了。
*/
#include <fstream>
#include <iostream>
#include <string>
#include <memory>
#include <algorithm>
#define cin fin
using namespace std;
ifstream fin("kimbits.in");
ofstream fout("kimbits.out");
string disp(int num,int sz)
{
       string s,as;
       int t;
       as.assign("1");
       for(int i=31;i>=0;i--)
       {
           t=num&1;
           num=num>>1;
           if(!t) as[0]='0';
           else as[0]='1';
           s.append(as);
       }
       t=s.size()-1;
       while(s[t]=='0') {s.erase(t,t+1);t--;}
      
	   while(s.size()<sz) s.append("0"); 
       reverse(s.begin(),s.end());
       return s;
}
int main()
{
    unsigned int i,j,m,k,ii,jj,sum,pre;
    unsigned long num=0;
    int n,l;
    cin>>n>>l>>k;    
    int a[32][32];
    memset(a,0,sizeof(a));
    for(i=0;i<32;i++) {a[i][0]=1;a[0][i]=1;}
    for(i=1;i<32;i++){
     //  a[i][1]=1;
       for(j=1;j<32;j++)
            a[i][j]=a[i-1][j-1]+a[i-1][j];
    }//for
    sum=k;
    j=0;   
    for(ii=n;ii>0;ii--)
    {
        int temp=1;
        temp=temp<<(ii-1);
        if(sum>a[ii-1][l-j]) 
        {
            num=num|temp;
            sum-=a[ii-1][l-j];
            j++;
        }
    }
    
    fout<<disp(num,n)<<endl;
//	system("PAUSE");
    return 0;
}