2.奶牛编号
【问题描述】
作为一个神秘的电脑高手，Farmer John 用二进制数字标识他的奶牛。
然而，他有点迷信，标识奶牛用的二进制数字，必须只含有K位“1”
(1 <= K <= 10)。 当然，每个标识数字的首位必须为“1”。
FJ按递增的顺序，安排标识数字，开始是最小可行的标识数字
（由“1”组成的一个K位数）。
不幸的是，他没有记录下标识数字。请帮他计算，第N个标识数字
(1 <= N <= 10^7)。
【输入】
第1行：空格隔开的两个整数，N和K。
【输出】
如题，第N个标识数字
【输入输出样例】
|
cowids.in |
cowids.out |
|
7 3 |
10110 |
输出第n大的包含k个1的01串。
首先第一位必须是1，所以后面还有k-1个1要放。k=1的时候直接特判。
在长度为len的01串中放入k-1个1的方案数就是C(len,k-1)
如果n比C(len,k-1)大，那么len++，n-=C(len,k-1)。继续找下一个。
这样就确定了后面有几位。
然后直接暴力出奇迹不解释
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<deque> 9 #include<set> 10 #include<map> 11 #include<ctime> 12 #define LL long long 13 #define inf 0x7ffffff 14 #define pa pair<int,int> 15 #define pi 3.1415926535897932384626433832795028841971 16 using namespace std; 17 int n,k,now; 18 int a[100000]; 19 inline LL C(int n,int m) 20 { 21 LL sum=1; 22 for (int i=n-m+1;i<=n;i++) 23 sum*=i; 24 for (int i=1;i<=m;i++) 25 sum/=i; 26 return sum; 27 } 28 inline void work(int n,int rnk)// 长度为n的01串有k个1的字典序rnk小的方案 29 { 30 for (int i=n-k+1;i<=n;i++)a[i]=1; 31 rnk--; 32 while (rnk--) 33 { 34 int tot=0,fst;for (fst=n;fst>=1;fst--)if (a[fst])break; 35 for (;fst>=1;fst--) 36 { 37 if (!a[fst])break; 38 tot++; 39 } 40 for (int i=n;i>=fst;i--)a[i]=0; 41 for (int i=n;i>=n-tot+2;i--)a[i]=1; 42 a[fst]=1; 43 } 44 for (int i=1;i<=n;i++) printf("%d",a[i]); 45 } 46 int main() 47 { 48 freopen("cowids.in","r",stdin); 49 freopen("cowids.out","w",stdout); 50 scanf("%d%d",&n,&k); 51 if (k==1) 52 { 53 printf("1"); 54 for(int j=1;j<n;j++)printf("0"); 55 return 0; 56 } 57 k--; 58 now=k; 59 while (1) 60 { 61 if (n<=C(now,k)) 62 { 63 printf("1"); 64 work(now,n); 65 return 0; 66 } 67 n-=C(now,k); 68 now++; 69 } 70 }