蓝桥杯2021年第十二届国赛真题—二进制问题

解题思路:要想知道1到N中有多少个数满足其二进制表示中恰好有K个1，

递推：根据Cnm=C(n-1)(m-1)+C(n-1)m;来求出所有位置的组合数值，然后当原来N的二进制位置为1时，加上对应组合数；为0时，继续递推；

递归：那么我们可以先将N进行转换成二进制，将其值保存在一个数组中，这里设为a数组，最高为p位。

       然后再从N转化的二进制最高位开始讨论，将K个1组合分布在p个位置上。若N对应的二进制数上原本是1，那么我们在此位取1或者0都可以，取0得到的数一定比N小，取1的话就代表剩下的位置我们将分布p-1个1。

注意事项:组合数，数据范围用long long

参考代码:

//递推写法

#include

using namespace std;

long long N,K;

long long  f[70][70];

int main(){

    int i,j,p;

    cin>>N>>K;

    for(i=1;(1ull<<i)<=N;i++);//找十进制转二进制的最高位 

        p=i+1;

    for(i=1;i<=p;i++) f[i][0]=1;

        f[1][1]=1;

    for(i=2;i<=p;i++){   

        for(j=1;j<=i;j++)

            f[i][j]=f[i-1][j]+f[i-1][j-1];//求组合数

    }   

    long long ans=0,c=K;

    for(i=p-1;i>=1;i--){   

        if((1ull<<(i-1))&N) ans+=f[i-1][c--];//找对应的组合数

        if(c==0){

            ans++;

            break;

        }

    }   

    cout<<ans<<endl;

    return 0;

} 

//递归写法

#include

using namespace std;

int a[1000];

double fact(int n){//求阶乘 

     double count=1;

     for(int i=2;i<=n;i++){

        count*=i;

     }

    return count;

}

double C(int n,int m){//求组合数 

     double count=fact(n)/(fact(m)*fact(n-m));

     return count;

}

double F(int p,int k){//p当前位置  k需要排列几个1

     if(k==0) return 1;

     if(p==0) return 0;

     if(p<k) return 0;

     if(a[p]==0) 

     return F(p-1,k);

     else if(a[p]==1) 

     if(p-1>=k) return F(p-1,k-1)+C(p-1,k);

     else return F(p-1,k-1);

}

int main(){

     int p;//最大位数

     long long N,k;

     cin>>N>>k;

     while(N){//找最高位

         p++;

         a[p]=N%2;

         N/=2;

     }

     printf("%.0lf",F(p,k));

     return 0;

}