奶牛编号
##【题目描述】:
作为一个神秘的电脑高手,Farmer John 用二进制数字标识他的奶牛。
然而,他有点迷信,标识奶牛用的二进制数字,必须只含有K位“1”。当然,每个标识数字的首位必须为“1”。
FJ按递增的顺序,安排标识数字,开始是最小可行的标识数字(由“1”组成的一个K位数)。不幸的是,他没有记录下标识数字。请帮他计算,第N个标识数字。
##【输入描述】:
第1行:空格隔开的两个整数,N和K。
##【输出描述】:
如题,第N个标识数字。
##【样例输入】:
7 3
##【样例输出】:
10110
##【时间限制、数据范围及描述】:
时间:1s 空间:128M
1 <= K <= 10, 1 <= N <= 10^7
真基尔惭愧啊,呆孬都测好了laj还没想好这题 laj还是太laj辣 _(:зゝ∠)_
一开始想了些很玄学的做法,比如一个个往里面插0?不过这只停留在理论层面 _(:зゝ∠)_ 最后十分钟的时候laj终于想好了,可惜还是比别人迟了十分钟再交QAQ
1 #include "bits/stdc++.h"
2 using namespace std;
3 typedef long long LL;
4 LL n,k;
5 LL a[5005][100];
6 void work(){
7 int i,j;
8 memset(a,0,sizeof(a));10 for (i=1;i<=5000;i++){
11 a[i][0]=1;
12 for (j=1;j<=min(i,20);j++){
13 if (j==i) a[i][j]=1;
14 else a[i][j]=a[i-1][j]+a[i-1][j-1];
15 }
16 }
17 }
18 int main(){
19 freopen ("cowids.in","r",stdin);
20 freopen ("cowids.out","w",stdout);
21 int i,j,len;
22 scanf("%lld%lld",&n,&k);
23 work();
24 len=k;
25 if (n==1){for (i=1;i<=k;i++) putchar('1'); return 0;}
26 if (k==1) {printf("1");for (i=1;i<n;i++) putchar('0');return 0;}
27 while (a[len][k]<=n) len++; len--;k--;
28 for (i=k;i<len;i++) n-=a[i][k];
29 putchar('1');
30 for (i=1;i<=len;i++){
31 if (k==0){
32 putchar('0');
33 }
34 else if (a[len-i][k]>=n){
35 putchar('0');
36 }
37 else{
38 putchar('1');
39 n-=a[len-i][k];
40 k--;
41 }
42 }
43 return 0;
44