依然的风暴

用户名：fengbaoyihao300

访问量：370

签　名：

等　　级
排　　名	72761
经　　验	166
参赛次数	0
文章发表	1
年　　龄	0
在职情况	学生
学　　校	中国人民公安大学
专　　业

　　自我简介：

TA的其他文章

清晰好理解-----2021 python 蓝桥杯决赛“二进制问题”也不是太难
浏览：318

你可能喜欢

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

【绝对值排序】（C++代码）（利用两个库函数——abs()求绝对值和 sort()快排）

清晰好理解-----2021 python 蓝桥杯决赛“二进制问题”也不是太难

　　作者: 依然的风暴　　　　发表时间：2022-06-04 11:22:17 浏览：318　|　评论：0　

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

##废话不多说，直接上代码
```python
n, k = map(int, input().split())
bstr = str(bin(n))[2:]

def Cn(m, n):
    # 这个判断代表：当剩余二进制位数小于所需k值，即就算剩下的所有位都置1，依然无法满足条件
    if n < m:
        return 0
    # A计算
    a = 1
    for i in range(n, (n - m), -1):
        a *= i
    # 阶乘计算
    t = 1
    for i in range(1, m + 1):
        t *= i
    # C计算
    return a / t

cnt = 0
for i in range(0, len(bstr)):
    if k == 0:
        cnt += 1
        break
    if bstr[i] == '1':
        plus = int(Cn(k, len(bstr) - i - 1))
        # 下面这步判断代表：当所需k值<=剩余二进制位数时，是直接退出或是cnt+1退出
        if plus == 0:
            #  当二进制数最后一位正好==k值==1时(相当于输入 1 1 特殊情况)
            if int(bstr[i]) == k:
                cnt += 1
            break
        cnt += plus
        k -= 1
print(cnt, end='')

```
#####在使用python的情况下速度依然达到了159ms，案例也全部AC
---
##思路
1. 首先想到的是遍历所有可能出现的排列组合情况，但从题目给的数值范围来看肯定会TLE（超时），这种思路不符合实际情况。

2. 但是思路1的方向是正确的，我们知道傻傻的遍历肯定不行，只有聪明的遍历才能拿到AC，这也是剪枝的思路。

3. 于是我随便拿一个数12345，观察他的二进制形式 11000000111001，初步可以想到，拿前五位来说，人类一眼就能看出来11000肯定比11100小，可以直接删掉11100---之类的组合。嗯~~~~，思路来了。

4. 那这么说，我们可以从二进制的高位（即从左到右的顺序）开始，一步步往低位进发。从思路3可以看出，如果原二进制数org_b的某一位是1，排列组合出来的新数new_b的某一位也是1，那情况会比较复杂，需要与原二进制数比较并逐级向低位判断，但如果是new_b的这一位是0呢，不管后面二进制位怎么置1，都不可能比我现在大，所以这时候直接使用排列组合C(k,n)就行，n就是当前二进制位之后的位数。

5. 从思路4可以看出来，这就是循环判断的过程。如果org_b的一位是1，那么就进行思路4的判断，如果是0，则直接跳过（因为二进制位当中，没有比0更小的数了，锁死了new_b的选择）。

6. 选择了一个1，就将k值-1，直到最后k值归零，输出cnt即可（也有可能会存在剩余位数小于k值或正好等于k值，cnt+0或+1即可）

##结论
至此，流程结束。作为蓝桥杯决赛倒数第二题，有一定的难度和灵活度，但不需要用到dp还是挺友好的:kissing_heart:

0.0分

1 人评分

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

依然的风暴

TA的其他文章

你可能喜欢

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

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

【绝对值排序】（C++代码）（利用两个库函数——abs()求绝对值和 sort()快排）

【出圈】（C语言代码）

用筛法求之N内的素数。（C语言代码）

清晰好理解-----2021 python 蓝桥杯决赛“二进制问题”也不是太难

评论区

精彩推荐

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

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

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

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

大家好，我是验题君

C二级辅导-温度转换（C语言代码）

C二级辅导-阶乘数列（C语言代码）

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

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

矩阵转置（C语言代码）

依然的风暴

TA的其他文章

你可能喜欢

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

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

【绝对值排序】 （C++代码）（利用两个库函数——abs()求绝对值 和 sort()快排）

【出圈】 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

清晰好理解-----2021 python 蓝桥杯决赛“二进制问题”也不是太难

评论区

精彩推荐

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

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

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

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

大家好，我是验题君

C二级辅导-温度转换 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

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

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

矩阵转置 （C语言代码）

【绝对值排序】（C++代码）（利用两个库函数——abs()求绝对值和 sort()快排）

【出圈】（C语言代码）

用筛法求之N内的素数。（C语言代码）

　　评论区

C二级辅导-温度转换（C语言代码）

C二级辅导-阶乘数列（C语言代码）

矩阵转置（C语言代码）