[2014-10-29 模拟赛] 奶牛编号

描述 Description

作为一个神秘的电脑高手,Farmer John 用二进制数字标识他的奶牛。

然而,他有点迷信,标识奶牛用的二进制数字,必须只含有 K 位“1” (1 <= K <= 10)。 当然,每个标识数字的首位必须为“1”。

FJ 按递增的顺序,安排标识数字,开始是最小可行的标识数字(由 “1” 组成的一个 K 位数)。

不幸的是,他没有记录下标识数字。请帮他计算,第 N 个标识数字 (1 <= N <= 10^7)。

输入格式 InputFormat

第 1 行:空格隔开的两个整数,N 和 K。

输出格式 OutputFormat

如题,第 N 个标识数字。

样例输入 SampleInput

9876 7

样例输出 SampleOutput

1100011100001001


NOIP 模拟赛


代码 Code

用 a[i][j]表示 i 位放 j 个 1 的方案数,可以发现这是个杨辉三角。。so 一步步逼近答案即可。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define ll long long
int i,j,t,n,m,l,r,k,z,y,x;
int a[500005][11];
char ch[100005];
void find(int s)
{
    int i,j,t;
    if (s==0 || m==0) return ;
    t=a[s+1][m+1]-a[s][m];
    if (t>=n)
    {
        ch[s]='0';
        find(s-1);
    }
    else
    {
        ch[s]='1';
        m--;
        n-=t;
        find(s-1);
    }
}
int main()
{
    freopen("cowids.in","r",stdin);
    freopen("cowids.out","w",stdout);
    scanf("%d%d",&n,&m);
    if (m==1)
    {
        printf("1");
        for (i=1;i<n;i++) printf("0");
        printf("\n");
        return 0;
    }
    t=0;
    a[1][1]=1;
    for (i=0;i<=100000;i++) ch[i]='0';
    for (i=2;a[i][m]<n;i++)
    {
        for (j=1;j<=m;j++) a[i][j]=a[i-1][j-1]+a[i-1][j];
    }
    t=m;
    while (n-a[t][m]>0) n-=a[t][m],t++;
    ch[t]='1';m--;
    find(t-1);
    while (t) printf("%d",(int)(ch[t]-'0')),t--;
    printf("\n"); 
    return 0;
}