[USACO12FEB]牛的IDCow IDs

题目描述

Being a secret computer geek, Farmer John labels all of his cows with binary numbers. However, he is a bit superstitious, and only labels cows with binary numbers that have exactly K "1" bits (1 <= K <= 10). The leading bit of each label is always a "1" bit, of course. FJ assigns labels in increasing numeric order, starting from the smallest possible valid label -- a K-bit number consisting of all "1" bits. Unfortunately, he loses track of his labeling and needs your help: please determine the Nth label he should assign (1 <= N <= 10^7).

FJ给他的奶牛用二进制进行编号，每个编号恰好包含K 个"1" (1 <= K <= 10)，且必须是1开头。FJ按升序编号，第一个编号是由K个"1"组成。

请问第N(1 <= N <= 10^7)个编号是什么。

输入输出格式

输入格式：

Line 1: Two space-separated integers, N and K.

输出格式：

输入输出样例

输入样例#1：

7 3

输出样例#1：

10110

我们先将这个串用足够大小保存，足够大的话我们可以添加前导0，到最后从第一个非0位输出即可，也就是说我们要找到一个m,使得C(m,k) >= n，可以二分求m

这题最坑的是为了防止溢出longlong，所以要将k分情况制定二分右界

如果做到第i位，还要填j个1，那么这一位填0的方案数就是C(i-1,j)，即还剩i-1位可以填j个1的方案数。

如果这个数小于n，那么这一位填1，并且n要减去这个数，否则这一位填0。

myys

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 typedef long long ll;

 ll n;

 int k,cnt,m,ans[];

 ll C(int x,int y)

 {int i;

   if (x>y) return ;

   ll s=;

   for (i=y;i>y-x;i--)

     s*=i;

   for (i=x;i>=;i--)

     s/=i;

   return s;

 }

 int main()

 {int i;

   cin>>n>>k;

   if (k==)

     {

       cout<<;

       for (i=n-;i>=;i--)

     {

       printf("");

     }

       return ;

     }

   int l=,r;

   if (k>=)

   r=;

   else if (k>=)

     r=;

   else r=;

   while (l<=r)

     {

       int mid=(l+r)/;

       if (C(k,mid)>=n) m=mid,r=mid-;

       else l=mid+;

     }

   cnt=;

   for (i=m;i>=;i--)

     {

       ll p=C(k,i-);

       if (p<n)

     {

       k--;

       ans[i]=;

       n-=p;

       if (cnt==)

         {

           cnt=i;

         }

     }

       if (k==||n==)

     {

       break;

     }

     }

   for (i=cnt;i>=;i--)

     printf("%d",ans[i]);

 }

巴特西

[USACO12FEB]牛的IDCow IDs

题目描述

输入输出格式

输入输出样例

最新文章

热门文章