欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-08 18:24:18
Description 作为一个神秘的电脑高手,Farmer John 用二进制数字标识他的奶牛。 然而,他有点迷信,标识奶牛用的二进制数字,必须只含有K位“1” (1 <= K <= 10)。当然,每个标识数字的首位必须为“1”。 FJ按递增的顺序,安排标识数字,开始是最小可行的标识数字(由“1”组成的一个K位数)。 不幸的是,他没有记录下标识数字。请帮他计算,第N个标识数字 (1 <= N <= 10^7)。Input......

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