不含101的数
真题目录: 点击去查看
E 卷 200分题型
题目描述
小明在学习二进制时，发现了一类不含101的数：
将数字用二进制表示，不能出现 101 。
现在给定一个整数区间 [l,r] ，请问这个区间包含了多少个不含 101 的数？
输入描述
输入的唯一一行包含两个正整数 l， r（ 1 ≤ l ≤ r ≤ 10^9）。
输出描述
输出的唯一一行包含一个整数，表示在 [l,r] 区间内一共有几个不含 101 的数。
用例1
输入
1 10
输出
8
说明
区间 [1,10] 内， 5 的二进制表示为 101 ，10的二进制表示为 1010 ，因此区间 [ 1 , 10 ] 内有 10−2=8 个不含 101的数。
用例2
输入
10 20
输出
7
说明
区间 [10,20] 内，满足条件的数字有 [12,14,15,16,17,18,19] 因此答案为 7。
题解
思路：
采用数组dp算法 + 记忆化搜索剪枝实现：
- dfs(int p, boolean limit, int[] [] f, Integer[] arr, int pre, int prepre)： p 当前位置，limit之前的是否为最大值? 会限制当前的取值范围, f 记忆化数组防止重复计算. pre前一位的值，prepre前两位的值
c++
#include <stdio.h>
#include <string.h>
#include<iostream>
#define MAX_LEN 32 // 假设 int 最大 32 位int dp[MAX_LEN][2][2];
int binary[MAX_LEN]; // 存储二进制数，从高位到低位// 递归计算
int dfs(int pos, int limit, int pre, int prepre, int len) {if (pos == len) return 1; // 递归到末尾，找到一个有效方案if (!limit && dp[pos][pre][prepre] != -1) return dp[pos][pre][prepre];int maxDigit = limit ? binary[pos] : 1; // **存储高位到低位，所以直接用 pos**int count = 0;for (int i = 0; i <= maxDigit; i++) {if (i == 1 && pre == 0 && prepre == 1) continue; // 跳过非法情况count += dfs(pos + 1, limit && (i == maxDigit), i, pre, len);}if (!limit) dp[pos][pre][prepre] = count; // 记忆化存储return count;
}// 计算 0~num 内的合法数字个数
int digitSearch(int num) {int len = 0;memset(dp, -1, sizeof(dp));// **高位到低位存储二进制数**for (int i = 31; i >= 0; i--) {if (num & (1 << i)) {binary[len++] = 1;} else if (len > 0) { // 遇到第一个1后才开始存储binary[len++] = 0;}}return dfs(0, 1, 0, 0, len);
}int main() {int L, R;scanf("%d %d", &L, &R);int count = digitSearch(R) - digitSearch(L - 1);printf("%d\n", count);return 0;
}JAVA
import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int L = sc.nextInt();int R = sc.nextInt();int count = digitSearch(R) - digitSearch(L - 1);System.out.println(count);}public static int digitSearch(int num) {Integer[] arr =Arrays.stream(Integer.toBinaryString(num).split("")).map(Integer::parseInt).toArray(Integer[]::new);int[][][] f = new int[arr.length][2][2];return dfs(0, true, f, arr, 0, 0);}public static int dfs(int p, boolean limit, int[][][] f, Integer[] arr, int pre, int prepre) {if (p == arr.length) return 1;if (!limit && f[p][pre][prepre] != 0) return f[p][pre][prepre];int max = limit ? arr[p] : 1;int count = 0;for (int i = 0; i <= max; i++) {if (i == 1 && pre == 0 && prepre == 1) continue;count += dfs(p + 1, limit && i == max, f, arr, i, pre);}if (!limit) f[p][pre][prepre] = count;return count;}
}
Python
# 算法实现
def dfs(p, limit, f, arr, pre, prepre):if p == len(arr):return 1if not limit and f[p][pre][prepre] > 0:return f[p][pre][prepre]maxV = arr[p] if limit else 1count = 0for i in range(maxV + 1):if i == 1 and pre == 0 and prepre == 1:continuecount += dfs(p + 1, limit and i == maxV, f, arr, i, pre)if not limit:f[p][pre][prepre] = countreturn countdef digitSearch(num):arr = list(map(int, list(format(num, 'b'))))f = [[[0 for k in range(2)] for j in range(2)] for i in range(len(arr))]return dfs(0, True, f, arr, 0, 0)# 输入获取
L, R = map(int, input().split())# 算法调用
print(digitSearch(R) - digitSearch(L - 1))
JavaScript
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;void (async function () {const times = (await readline()).split(",").map(Number);const m = parseInt(await readline());// T的初始取值范围let low = 0;let high = times.reduce((a, b) => a + b) - Math.max(...times);// 二分while (low <= high) {// 取中间值尝试let mid = (low + high) >> 1;if (check(mid)) {high = mid - 1;} else {low = mid + 1;}}console.log(low);function check(t) {// 今天总耗时let sum_cost = 0;// 今天耗时最多的题目的耗时let max_cost = 0;// 今天是否可以申请帮助let canHelp = true;// 第几天let day = 1;let i = 0;while (i < times.length) {sum_cost += times[i];max_cost = Math.max(max_cost, times[i]);if (sum_cost > t) {// 如果做完times[i]，总耗时超过了tif (canHelp) {// 如果可以申请帮助，那么就看耗时最长的题目的答案sum_cost -= max_cost;// 今天申请帮助的机会用完了canHelp = false;// 下面继续做下一题i++;} else {// 如果不能申请帮助，则今天做不了times[i]题目，只能放到明天做// 进入明天day++;// 重置总耗时，最大耗时题目，以及申请帮助机会sum_cost = 0;max_cost = 0;canHelp = true;}} else {// 如果做完times[i]，总耗时没有超过t，则继续做下面的题目i++;}}return day <= m;}
})();
Go
package mainimport ("fmt"
)const MaxLen = 32 // 最大二进制位数var dp [MaxLen][2][2]int
var binary []int// 递归计算
func dfs(pos int, limit bool, pre int, prepre int, length int) int {if pos == length {return 1 // 递归到末尾，找到一个有效方案}if !limit && dp[pos][pre][prepre] != -1 {return dp[pos][pre][prepre]}maxDigit := 1if limit {maxDigit = binary[pos] // 访问当前位}count := 0for i := 0; i <= maxDigit; i++ {if i == 1 && pre == 0 && prepre == 1 {continue // 跳过非法情况}count += dfs(pos+1, limit && (i == maxDigit), i, pre, length)}if !limit {dp[pos][pre][prepre] = count // 记忆化存储}return count
}// 计算 0~num 内的合法数字个数
func digitSearch(num int) int {binary = []int{}started := false // 标记是否遇到了第一个 1// **高位到低位存储二进制数**for i := 31; i >= 0; i-- {if num&(1<<i) > 0 {binary = append(binary, 1)started = true} else if started { // 遇到第一个 1 后才开始存储后续 0binary = append(binary, 0)}}length := len(binary) // 记录二进制长度// 初始化 dp 数组for i := range dp {for j := range dp[i] {for k := range dp[i][j] {dp[i][j][k] = -1}}}return dfs(0, true, 0, 0, length)
}func main() {var L, R intfmt.Scan(&L, &R)count := digitSearch(R) - digitSearch(L-1)fmt.Println(count)
}
