2932. 【NOIP2012模拟8.7】奶牛编号

Description

    作为一个神秘的电脑高手，Farmer John 用二进制数字标识他的奶牛。 

    然而，他有点迷信，标识奶牛用的二进制数字，必须只含有K位“1” (1 <= K <= 10)。 当然，每个标识数字的首位必须为“1”。 

    FJ按递增的顺序，安排标识数字，开始是最小可行的标识数字（由“1”组成的一个K位数）。 

    不幸的是，他没有记录下标识数字。请帮他计算，第N个标识数字 (1 <= N <= 10^7)。   

Input

    第1行：空格隔开的两个整数，N和K。   

Output

    =10.5pt如题，第N个标识数字  

Sample Input

7 3

Sample Output

10110

Solution

对于第一个数，一定是k个1。

考虑每次加入多一个0，设当前加入了i个0，因为第一个位置一定是1，所以有k个空位，每个位置可以不放0。

那么转换为插板问题，一共i+k-1个空隙，放k-1个挡板，方案是C( i+k-1 , k-1 )。

预处理出组合数后，枚举i（或者二分）可以求出对于第n个k位1的数一共有几个0在原数中出现。

同样枚举当前这个0放在哪个1后面，设现在我们有 t 个0要放，我们要找到第x大的放t个0数

对于第 now 个1，如果放了1个0在第now个1后面，那么：

剩下：t-1个0，k-now+1个空隙，一共有C( k-now+1  +  t-1  -1 , k-now+1  -1 )=C( k-now+t-1 , k-now )种放法。

如果剩下的放法大于等于x，那么就在当前1后面放一个0，

如果剩下的放法比x小，那么我们就把所有的放在第now个1的放法放完，即x-=C( k-now+t-1 , k-now )，然后这个1后面就不妨0了，继续放下一个1，这样就能保证原数变大了，进而找到第x大的数。最后把所有1带着其后面跟着有多少个0输出即可。

Code

#include<cstdio> 
#include<cstring>
#include<algorithm>
#define I int
#define ll long long
#define F(i,a,b) for(I i=a;i<=b;i++)
#define Fd(i,a,b) for(I i=a;i>=b;i--)
using namespace std;
I n,k,now,x,t,a[55];
ll f[100011][12];
I main(){
	freopen("number.in","r",stdin);
	freopen("number.out","w",stdout);
	scanf("%d%d",&n,&k);x=n-1;
	if(k==1){
		printf("1");
		F(i,1,n-1) printf("0");
		return 0;
	}
	F(i,0,100000){
		f[i][0]=1;
		F(j,1,min(i,k)) f[i][j]=f[i-1][j]+f[i-1][j-1];
	}
	F(i,1,100000){
		if(x>=f[i+k-1][k-1]) x-=f[i+k-1][k-1];
		else{t=i;break;}
	}
	if(!x){
		F(i,1,k) printf("1");
		F(i,1,t) printf("0");
		return 0;
	}
	now=1;
	while(t){
		if(f[k-now+t-1][k-now]>=x){
			a[now]++;
			t--;
		}
		else{
			x-=f[k-now+t-1][k-now];
			now++;
		}
	}
	F(i,1,k){
		printf("1");
		F(j,1,a[i]) printf("0");
	}
	return 0;
}

 

本文地址：https://blog.csdn.net/zsjzliziyang/article/details/107880348