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