「NOIP模拟赛」奶牛编号
「问题描述」
作为一个神秘的电脑高手，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 |
题解
裸的搜索似乎能拿很多分
注意特判K=1的情况即1后面都是0。。。
利用找规律或者递推算出答案中的0的个数。。。
然后直接搜索
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<set> #define ll long long #define inf 100000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int now; int n,K,tot; bool ans[1000005]; void dfs(int x,int y) { if(x==K&&y==tot) { now++; if(now==n)return; } if(y<tot&&now!=n)ans[x+y]=false,dfs(x,y+1); if(x<K&&now!=n)ans[x+y]=true,dfs(x+1,y); } int main() { n=read();K=read(); if(K==1) { printf("1"); for(int i=1;i<n;i++) printf("0"); puts(""); return 0; } else { ll sum=1,i=1; for(;sum*(i+K)/i<=n;i++) sum=sum*(i+K)/i; tot=i;now=sum; ans[0]=1;dfs(1,0); for(int i=0;i<tot+K;i++)printf("%d",ans[i]); puts(""); return 0; } return 0; } |
Subscribe
计数器 9856830
OI 课件=>
OI 课件=>