xiaoluo

用户名：xiaoluo

访问量：99

签　名：

心之所向，素履以往

等　　级
排　　名	33420
经　　验	420
参赛次数	1
文章发表	1
年　　龄	19
在职情况	学生
学　　校	中国石油大学（华东）
专　　业	计算机科学与技术

　　自我简介：

菜鸟大学生

TA的其他文章

蓝桥杯2021年第十二届国赛真题-二进制问题 #C++#dfs
浏览：45

你可能喜欢

C语言程序设计教程（第三版）课后习题6.1 （C++代码）__gcd()是已经写好的函数，可以直接使用

蓝桥杯2021年第十二届国赛真题-二进制问题 #C++#dfs

　　作者: xiaoluo　　　　发表时间：2023-06-06 21:07:22 浏览：45　|　评论：0　

原题链接：蓝桥杯2021年第十二届国赛真题-二进制问题

```c++
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 1e5+5;

ll n,k;

ll ans;

//这个函数主要是为了判断n个位置放置m个1有多少种方案数
ll C(int n,int m){
    if(n < m)return 0ll;//剩余位置如果不如1的数量多当然要返回0啦
    ll res = 1;
    ll k = 1;
    if(m > n/2)m = n - m;
    for(ll i=n-m+1;i<=n;i++){
        res *= i;
        while(k<=m && res%k == 0){
            res /= k;
            k++;
        }
    }
    return res;
}
//这破dfs还是挺好理解的，主要就是所有情况要考虑好
//cnt和k有3种关系
//num和n有3种关系
//所以共有3*3=9种情况
//我们用1代表相等2代表大于3代表小于表示所有情况
//1= 2> 3<
//除了num<n&&cnt<k也就是33这一种情况需要递归之外，其他都可以直接返回定值
ll dfs(int idx,ll num,int cnt,int f){
    if(cnt>k)return 0ll;//12 22 32
    if(num>n)return 0ll;//21 22 23
    if(num==n && cnt<k)return 0ll;//13
    if(num==n && cnt==k)return 1ll;//11
    if(num<n && cnt==k)return 1ll;//31
    
    //tmp的作用是为了判断你前面通过补0或者补1得到的这几位数和n的对应位的大小关系
    //举个例子比如 10111***** 是n，而(10011)00000也就是num，而括号中的部分就是你当前补出来的几位数
    //我们比较的就是括号中这几位数的大小
    //我们先把括号之外的数全变成1 (10011)11111
    //然后和n即10111*****按位与
    //就会得到(10011)*****然后与n比较就可以知道括号中的数和n的这几位的大小关系了
    //如果括号中的数比n的这几位要小，那么剩余的位置随便补1最终结果都不会大于n，所以直接C(idx,k-cnt)
    //但是如果相等(不会出现大于的情况),那么就需要继续递归啦，也就是考虑下一位补1还是补0两种情况
    ll tmp = num + (1ll<<idx) - 1ll;//剩余位都补成1
    tmp = tmp & n;//与n相与，再与n比较

if(tmp < n){//如果前几位小于n的前几位，后面剩下的k-cnt个1怎么分配都可以，也就是idx位任选k-cnt个位置放1
        return C(idx,k-cnt);
    }
    else{//否则答案就需要继续递归咯
        return dfs(idx-1,num+(1ll<<(idx-1)),cnt+1,1) + dfs(idx-1,num,cnt,0);
    }
}

int main() {
    scanf("%lld%lld",&n,&k);
    ans += dfs(60,(1ll<<60),1,1);
    ans += dfs(60,0ll,0,0);
    printf("%lld",ans);
    return 0;
}

```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

xiaoluo

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C++代码）__gcd()是已经写好的函数，可以直接使用

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

永远的丰碑（C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

蓝桥杯2021年第十二届国赛真题-二进制问题 #C++#dfs

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

核桃的数量（C语言代码）

A+B for Input-Output Practice (VII) （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C二级辅导-分段函数（C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

xiaoluo

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C++代码）__gcd()是已经写好的函数，可以直接使用

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

永远的丰碑 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

蓝桥杯2021年第十二届国赛真题-二进制问题 #C++#dfs

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

核桃的数量 （C语言代码）

A+B for Input-Output Practice (VII) （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C二级辅导-分段函数 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

永远的丰碑（C语言代码）

　　评论区

核桃的数量（C语言代码）

C二级辅导-分段函数（C语言代码）