目录

题目描述

输入描述

输出描述

用例

题目解析

算法源码

题目描述

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

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

输入描述

输入的唯一一行包含两个正整数 l， r（ 1 ≤ l ≤ r ≤ 10^9）。

输出描述

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

用例

题目解析

本题如果用暴力法求解，很简单

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});rl.on("line", (line) => {const [l, r] = line.split(" ").map(Number);console.log(getResult(l, r));
});function getResult(l, r) {let count = r - l + 1;for (let i = l; i <= r; i++) {if (Number(i).toString(2).indexOf("101") !== -1) {count--;}}return count;
}

但是本题的1 ≤ l ≤ r ≤ 10^9，也就是说区间范围最大是 1 ~ 10^9，那么上面O(n)时间复杂度的算法会超时。

因此，我们需要找到一个性能更优的算法。

本题需要使用数位DP算法，具体逻辑原理请看

数位DP - 带3的数_伏城之外的博客-CSDN博客

数位DP - 带49的数_伏城之外的博客-CSDN博客

算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});rl.on("line", (line) => {const [L, R] = line.split(" ").map(Number);const count = digitSearch(R) - digitSearch(L - 1);console.log(count);
});function digitSearch(num) {const arr = num.toString(2).split("").map(Number);const f = new Array(arr.length).fill(0).map(() => new Array(2).fill(0).map(() => new Array(2)));return dfs(0, true, f, arr, 0, 0);
}function dfs(p, limit, f, arr, pre, prepre) {if (p === arr.length) return 1;if (!limit && f[p][pre][prepre]) return f[p][pre][prepre];const max = limit ? arr[p] : 1;let count = 0;for (let 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;
}