刷题笔记合集🔗

不含101的数

问题描述

小柯在学习二进制时，发现了一类不含 101 的数，也就是：

将数字用二进制表示，不能出现 101 。
现在给定一个整数区间 ，请问这个区间包含了多少个不含 101 的数？

输入格式

输入的唯一一行包含两个正整数 ， （）。

输出格式

输出的唯一一行包含一个整数，表示在 区间内一共有几个不含 101 的数。

样例输入

1 10

10 20

样例输出

8

7

样例	解释说明
样例1	区间 内， 的二进制表示为 ， 的二进制表示为 ，因此区间 内有 个不含 101 的数。
样例2	区间 内，满足条件的数字有 因此答案为 。

数据范围

题解

这道题要求我们统计整数区间 中有多少个二进制表示不含 "101" 的数字。

思路分析

最直接的方法是遍历区间内的每个数，将其转换为二进制形式，然后检查是否包含 "101"。但由于题目给出的区间范围可能非常大（最大可达 ），这种暴力枚举方法会超时。

这类问题可以采用数位DP（数字动态规划）的方法解决。数位DP适合解决与数字的二进制/十进制表示相关的计数问题。

数位DP解法

我们定义状态： 表示当前处理到二进制的第 位，前一位数字是 ，前前一位数字是 时，可能的数字个数。

关键思路：

1. 从高位到低位依次处理二进制位
2. 记录当前处理到的位置前两位的值，判断是否会形成 "101"
3. 对于每一位，尝试填充0或1，但不能导致出现 "101" 序列
4. 处理边界情况：不能超过原数值的限制

数位DP中的一个关键优化是记忆化，这样我们不会重复计算相同状态。

时间复杂度分析

数位DP的时间复杂度与数字的二进制位数相关。一个 级别的数字，其二进制位数约为 。

时间复杂度：，即二进制位数 × 前一位可能值 × 前前一位可能值。 空间复杂度：

在这个问题中，时间复杂度实际上是 ，是常数级别的，因此可以很快得到结果。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 通过数位DP计算不包含101的数字个数
def cnt(num):
    # 将数字转为二进制并转为list
    bin_lst = list(bin(num)[2:])
    digs = [int(x) for x in bin_lst]
    n = len(digs)
    
    # 初始化记忆化数组，f[i][j][k]表示考虑前i位，前一位为j，前前一位为k时的合法数字个数
    f = [[[-1 for _ in range(2)] for _ in range(2)] for _ in range(n)]
    
    # dfs函数用于计算合法数字个数
    def dfs(pos, pre, ppre, lim):
        # 已处理完所有位，得到一个合法数字
        if pos == n:
            return 1
            
        # 如果不受上限限制且已经计算过，直接返回结果
        if not lim and f[pos][pre][ppre] != -1:
            return f[pos][pre][ppre]
        
        # 确定当前位可以填的上限
        up = digs[pos] if lim else 1
        ans = 0
        
        # 尝试填0或1
        for d in range(up + 1):
            # 如果填1且前两位是1和0，形成101，则跳过
            if d == 1 and pre == 0 and ppre == 1:
                continue
            # 递归计算下一位
            ans += dfs(pos + 1, d, pre, lim and d == up)
            
        # 记忆化存储
        if not lim:
            f[pos][pre][ppre] = ans
            
        return ans
    
    # 初始时没有前两位，用0表示
    return dfs(0, 0, 0, True)

# 主函数
l, r = map(int, input().split())
# 计算[1,r]中的合法数字个数，减去[1,l-1]中的合法数字个数
print(cnt(r) - cnt(l-1))

• Cpp

#include <bits/stdc++.h>
using namespace std;

// 计算[1,n