USACO Training Section 3.2 Stringsobits

英文原题  中文题译

大意：求至多有L个1的第i个N位二进制数（1<=L<=N<=31)。
举个例子：N=5,L=3,i=19，则为10011。考虑小于10000的(4位数)中至多3个1的有c(4,0)+c(4,1)+c(4,2)+c(4,3)=15个，大于等于10000小于10010的2个，大于等于10010小于10011的一个，则10011为所求。

从这个分析中可以看到这是个组合问题，tri[i][j]为在i位数中有j个位为1的数值的个数即c(i,j)，可以通过杨辉三角求得，然后计算得tri_sum[i][j]为在i位数中至多有j位为1的数值的个数。给定N,L,i, N其实是无用的，只用来限定表的计算。然后找到第一个100...00使得小于它的最多L位为1的数大于i，这就确定了最高位。之后逐位扫描，多了就出0，少了就给1。基本上是常熟时间得解。

唯一要注意的是i和数组需要long long或者unsigned int来存，否则越界。

/*
ID: blackco3
TASK: kimbits
LANG: C++
*/
#include <iostream>
#include <memory.h>
using namespace std;
#define _max_ 32
long long tri[_max_+1][_max_+1], tri_sum[_max_+1][_max_+1];
void yanghui_tri(int n) {
	memset( tri, 0, sizeof(tri) );
	for( int i=0; i<=n; i++ ){
		tri[i][0]=tri_sum[i][0]=1 ;
		for( int j=1; j<=i; j++ ){
			tri[i][j] = tri[i-1][j-1] + tri[i-1][j] ;
			tri_sum[i][j] = tri_sum[i][j-1] + tri[i][j];
		}
		for( int j=i+1; j<=n; j++ )
			tri_sum[i][j] = tri_sum[i][i] ;
	}
}

int main() {
	freopen("kimbits.in", "r", stdin);
	freopen("kimbits.out", "w", stdout);
	long long n_bit, n_one, n_th;
	cin >> n_bit >> n_one >> n_th ;
	yanghui_tri(n_bit+1);
	int bit;
	for( bit=0; tri_sum[bit][n_one]<n_th ; bit++ ) ;
	for( int i=n_bit; i>bit; i--)
		cout << 0 ;
	for( long long count=0; bit>0; bit-- ){
		if( tri_sum[bit-1][n_one]+count >= n_th ) 
			cout << 0 ;
		else {
			count += tri_sum[bit-1][n_one--] ;
			cout << 1 ;
		}
	}
	cout << endl ;
	return 0;
}