首页 > 代码库 > 2104.10.29模拟赛【奶牛编号】
2104.10.29模拟赛【奶牛编号】
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 long13 #define inf 0x7ffffff14 #define pa pair<int,int>15 #define pi 3.141592653589793238462643383279502884197116 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 }
2104.10.29模拟赛【奶牛编号】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。