刷题笔记合集🔗

问题描述

小兰在学习二进制时，发现了一类特殊的数字：不含 "101" 的数。具体来说，就是将数字转换成二进制表示后，其中不能出现连续的 "101" 序列。

例如：

• 数字 5 的二进制表示是 "101"，所以它不是一个合法的数
• 数字 10 的二进制表示是 "1010"，所以它也不是一个合法的数
• 数字 12 的二进制表示是 "1100"，它是一个合法的数

现在给定一个区间 ，请你帮小兰计算这个区间内有多少个不含 "101" 的数。

输入格式

输入一行，包含两个正整数 和 （），表示区间的左右端点。

输出格式

输出一个整数，表示区间 内不含 "101" 的数的个数。

样例输入1

1 10

样例输出1

8

样例输入2

10 20

样例输出2

7

样例解释

数据范围

• 
• 时间限制：1秒
• 空间限制：256MB

题解

这是一个数位DP问题，主要思路如下：

1. 问题分析

• 直接枚举区间内所有数字并判断会超时
• 需要使用数位DP来优化计算过程
• 关键是要记录前两位数字的状态

2. 解题思路

• 将问题转化为求解[1,r]的答案减去[1,l-1]的答案
• 对每个数字，将其转换为二进制
• 使用记忆化搜索，记录每个位置的状态
• 状态包括：当前位置、是否受限、前一位、前两位

3. 状态转移

• 对于每一位，可以填0或1
• 如果前两位是1,0，当前位不能填1
• 需要考虑数字的二进制长度限制

时间复杂度：O(log R)，其中R是区间右端点。

参考代码

def dfs(pos, limit, f, num, pre, prepre):
    """数位DP搜索
    pos: 当前处理到的位置
    limit: 是否受到上限限制
    f: 记忆化数组
    num: 目标数字的二进制表示
    pre: 前一位数字
    prepre: 前两位数字
    """
    # 处理完所有位置
    if pos == len(num):
        return 1
        
    # 如果不受限且已计算过，直接返回
    if not limit and f[pos][pre][prepre] > 0:
        return f[pos][pre][prepre]
        
    # 计算当前位置可以填的最大数字
    up = num[pos] if limit else 1
    ans = 0
    
    # 枚举当前位置可以填的数字
    for i in range(up + 1):
        # 如果前两位是1,0，当前位不能是1
        if i == 1 and pre == 0 and prepre == 1:
            continue
        # 继续处理下一位
        ans += dfs(pos + 1, limit and i == up, f, num, i, pre)
        
    # 记录结果
    if not limit:
        f[pos][pre][prepre] = ans
        
    return ans

def solve(n):
    """计算[1,n]范围内的答案"""
    # 转换为二进制
    bits = list(map(int, bin(n)[2:]))
    # 初始化记忆化数组
    f = [[[0]*2 for _ in range(2)] for _