不含101的数
不含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)
}
相关文章:
不含101的数
不含101的数 真题目录: 点击去查看 E 卷 200分题型 题目描述 小明在学习二进制时,发现了一类不含101的数: 将数字用二进制表示,不能出现 101 。 现在给定一个整数区间 [l,r] ,请问这个区间包含了多少个不含 101 的数ÿ…...
Linux/C高级(精讲)----shell结构语句、shell数组
shell脚本 功能性语句 test 可测试对象三种:字符串 整数 文件属性 每种测试对象都有若干测试操作符 1)字符串的测试: s1 s2 测试两个字符串的内容是否完全一样 s1 ! s2 测试两个字符串的内容是否有差异 -z s1 测试s1 字符串的长度是…...
基于微信小程序的消防隐患在线举报系统设计与实现(LW+源码+讲解)
专注于大学生项目实战开发,讲解,毕业答疑辅导,欢迎高校老师/同行前辈交流合作✌。 技术范围:SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容:…...
java基础2(黑马)
一、变量里的数据在计算机中的存储原理 1.二进制 .二进制:只有0、1, 按照逢二进一的方式表示数据。 十进制数字11转换为:1011 方法:除二取余法 计算机中表示数据的最小单元,一个字节(Byte,简…...
计算机中数值表示:原码、反码、补码与移码
1 前言 计算机科学中,数字的表示方式至关重要,因为计算机内部只能识别处理二进制数据。为了在计算机中实现对整数的表示,提出了多种数值编码方式,其中最常用的是原码、反码、补码和移码。 2 原码 2.1 原码的定义 原码(Signed …...
1.8 组合模式(Composite Pattern)
定义 组合模式(Composite Pattern) 是一种结构型设计模式,它将对象组合成树形结构以表示“部分-整体”的层次结构。组合模式让客户端可以以相同的方式对待单个对象和对象集合。组合模式使得客户可以统一处理树形结构中的单个对象和对象的集合…...
QFileDialog::getOpenFileName(this,“文件对话框“,“.“,“c++ files(*.cpp);;“); 文件对话框显示乱码
在使用 QFileDialog::getOpenFileName 时,如果文件对话框显示乱码,通常是因为编码问题。Qt 默认使用 UTF-8 编码,但如果你的系统或源代码文件的编码不一致,可能会导致乱码。 以下是几种可能的解决方法: 1. 确保源代码…...
【C语言系列】深入理解指针(5)
深入理解指针(5) 一、sizeof和strlen的对比1.1sizeof1.2strlen1.3sizeof和strlen的对比 二、数组和指针笔试题解析2.1 一维数组2.2 字符数组2.2.1代码1:2.2.2代码2:2.2.3代码3:2.2.4代码4:2.2.5代码5&#…...
为什么使用nohup 和 启动的python脚本,日志没有在nohup.out中
当你使用 nohup 和 & 启动 Python 脚本时,输出通常会被重定向到 nohup.out 文件,但是有几个原因可能导致日志没有出现在这个文件中: Python 程序的输出被重定向了: 如果你的 Python 脚本中使用了 sys.stdout 或 sys.stderr 进…...
MySQL的存储引擎对比(InnoDB和MyISAM)
InnoDB 特点: 事务支持:InnoDB 是 MySQL 默认的事务型存储引擎,支持 ACID(原子性、一致性、隔离性、持久性)事务。行级锁定:支持行级锁,能够并发执行查询和更新操作,提升多用户环境…...
uniapp访问django目录中的图片和视频,2025[最新]中间件访问方式
新建中间件, middleware.py 匹配,以/cover_image/ 开头的图片 匹配以/episode_video/ 开头的视频 imageSrc: http://192.168.110.148:8000/cover_image/12345/1738760890657_mmexport1738154397386.jpg, videoSrc: http://192.168.110.148:8000/episode_video/12345/compres…...
Python递归复习题
寒假打卡第二十一天,当前mit6.100L进度(16/26) ,今天补一下递归复习题。 问题1:编写一个递归程序来计算正和n(n-2)(n-4)的整数(直到且不包括n-x<0) def sum_series(n…...
2025 年前端开发趋势展望,开启新征程
新年伊始,作为一名深耕 Web 前端开发领域的博主,我迫不及待地想和大家分享我对 2025 年前端开发趋势的洞察。过去一年里,前端领域的技术创新和变革令人目不暇接,而新的一年,更是充满无限可能。 框架与工具的持续演进 …...
90,【6】攻防世界 WEB Web_php_unserialize
进入靶场 进入靶场 <?php // 定义一个名为 Demo 的类 class Demo { // 定义一个私有属性 $file,默认值为 index.phpprivate $file index.php;// 构造函数,当创建类的实例时会自动调用// 接收一个参数 $file,用于初始化对象的 $file 属…...
Redis --- 使用GEO实现经纬度距离计算
什么是GEO? Spring Boot 项目中可以通过 Spring Data Redis 来使用 Redis GEO 功能,主要通过 RedisTemplate 和 GeoOperations 接口来操作地理位置数据。 Service public class GeoService {Autowiredprivate RedisTemplate<String, Object> red…...
同步 CDC
同步 CDC 当设计包括来自同一 MMCM/PLL 的时钟之间的同步 CDC 路径时,您可以使用以下技术来更好地控制时钟插入延迟和 时滞,并因此控制这些路径上的松弛。 重要提示: 如果 CDC 路径在源自不同 MMCM/PLL 的时钟之间,则跨越 …...
Linux环境下载Ollama慢或卡顿解决方案
一、下载方式 官方下载方式是到ollama官网下载ollama: https://ollama.com/ 复制下载链接执行: curl -fsSL https://ollama.com/install.sh | sh二、卡顿现象 执行后经常会出现下载失败或者进度条特别慢的情况,甚至直接退出下载: 三、…...
生成式AI安全最佳实践 - 抵御OWASP Top 10攻击 (下)
今天小李哥将开启全新的技术分享系列,为大家介绍生成式AI的安全解决方案设计方法和最佳实践。近年来生成式 AI 安全市场正迅速发展。据IDC预测,到2025年全球 AI 安全解决方案市场规模将突破200亿美元,年复合增长率超过30%,而Gartn…...
2025年家用音响市场分析:潜力无限,音质为王的新纪元
引言:音质革命引领市场新风尚 在数字化浪潮的推动下,家用音响市场正经历一场前所未有的变革,其增长潜力犹如破晓之光,照亮了音频技术的未来之路。随着消费者对高品质生活追求的不断提升,以及对智能家居生态融合的日益…...
neo4j-在Linux中安装neo4j
目录 切换jdk 安装neo4j 配置neo4j以便其他电脑可以访问 切换jdk 因为我安装的jdk是1.8版本的,而我安装的neo4j版本为5.15,Neo4j Community 5.15.0 不支持 Java 1.8,它要求 Java 17 或更高版本。 所以我需要升级Java到17 安装 OpenJDK 17 sudo yu…...
AI 场景下,函数计算 GPU 实例模型存储最佳实践
作者:有松 当前,函数计算 FC 已被广泛应用在各种 AI 场景下,函数计算支持通过使用容器镜像部署 AI 推理应用,并且提供多种选项来访问训练好的模型。为了帮助开发者高效地在函数计算上部署 AI 推理应用,并快速解决不同…...
股指入门:股指期货是什么意思?在哪里可以做股指期货交易?
股指期货是一种以股票指数为标的物的期货合约,也可以称为股票指数期货或期指。 股指期货是什么意思? 股指期货是一种金融衍生品,其标的资产是股票市场上的股指,例如标普500指数、道琼斯工业平均指数、上证50指数等。 股指期货允…...
【分布式理论六】分布式调用(4):服务间的远程调用(RPC)
文章目录 一、RPC 调用过程二、RPC 动态代理:屏蔽远程通讯细节1. 动态代理示例2. 如何将动态代理应用于 RPC 三、RPC 序列化四、RPC 协议编码1. 协议编码的作用2. RPC 协议消息组成 五、RPC 网络传输1. 网络传输流程2. 关键优化点 一、RPC 调用过程 RPC(…...
aliyun 的 ip 设置方法
aliyun 的 ip 设置方法 阿里云:网络编程 bind:cannot assign requested address errno:99 问题。 公网IP,,弹性公网IP,主私网IP 1. 公网IP, --> NAT --> 主私网IP ,设置方法: 服务器端 ip 为&…...
ASP.NET Core分布式缓存
目录 分布式缓存 概述 IDistributedCache接口中定义的主要方法及主要的扩展方法 用什么做缓存服务器 使用 封装分布式缓存操作 分布式缓存 概述 分布式系统中,内存缓存不满足要求的话,把缓存数据保存到专门的缓存服务器,所有Web应用通…...
【CUDA】内存模型
目录 一、Programmable 1.1 寄存器(Registers) 1.2 本地内存(Local Memory) 1.3 共享内存(shared Memory) 1.4 常量内存(Constant Memory) 1.5 全局内存(Global Memory) 1.6 纹理内存(Textrue Memory) 1.7 总结 二、Cache(Non-programmable) 三、固定内存 四、零拷贝…...
使用Pygame制作“吃豆人”游戏
本篇博客展示如何使用 Python Pygame 编写一个简易版的“吃豆人(Pac-Man)” 风格游戏。这里我们暂且命名为 Py-Man。玩家需要控制主角在一个网格地图里移动、吃掉散布在各处的豆子,并躲避在地图中巡逻的幽灵。此示例可帮助你理解网格地图、角…...
Pyecharts系列课程04——折线图/面积图(Line)
本章我们学习在Pyecharts中折线图(Line)的使用。折线图通用应用于数据的趋势分析。 折线图 我们现在有两组数据,x_data是2024年的月份,y_data为对应张三甲每个月的用电量。 # 家庭每月用电量趋势 x_data ["1月", &q…...
mysql 学习10 多表查询 -多表关系,多表查询
多表关系 一对多 多对多 创建学生表 #多对多表 学生选课系统create table student(id int primary key auto_increment comment 主键ID,name varchar(64) comment 姓名,studentnumber varchar(10) comment 学号 )comment 学生表;insert into student(id,name,studentnumber)va…...
lambda 表达式详解
lambda 表达式详解 lambda 表达式详解基本语法示例代码及详细解释1. 简单的lambda表达式2. 带参数的lambda表达式3. 捕获外部变量4. 使用mutable关键字修改捕获的变量5. 按引用捕获外部变量6. 自动推导返回类型 捕获列表的几种形式总结 Lambda表达式的常用的应用场景࿱…...
从0开始达芬奇(3.5)
媒体优化 顾名思义就是降低分辨率等来使素材的回放更加流畅。(在低配电脑上也可以流畅运行) ⭐方法一:(一般使用第二种) 播放→代理模式→二分之一或者四分之一 ⭐⭐⭐方法二:优化媒体文件(简…...
【Uniapp-Vue3】z-paging插件组件实现触底和下拉加载数据
一、下载z-paing插件 注意下载下载量最多的这个 进入Hbuilder以后点击“确定” 插件的官方文档地址: https://z-paging.zxlee.cn 二、z-paging插件的使用 在文档中向下滑动,会有使用方法。 使用z-paging标签将所有的内容包起来 配置标签中的属性 在s…...
Ubuntu20.04 本地部署 DeepSeek-R1
一、下载ollama 打开 ollama链接,直接终端运行提供的命令即可。如获取的命令如下: curl -fsSL https://ollama.com/install.sh | sh确保是否安装成功可在终端输入如下命令: ollama -v注意: 如遇到Failed to connect to github.…...
Linux 设备驱动分类(快速理解驱动架构)
Linux 设备驱动分类(快速理解驱动架构) 在 Linux 设备驱动开发中,最基础的概念就是 设备驱动的分类。 Linux 设备驱动主要分为 字符设备、块设备和网络设备,它们分别对应不同类型的硬件资源。 理解这些分类,不仅能帮助…...
Java语法糖详解
前言 在现代编程语言的发展历程中,语法糖(Syntactic Sugar)作为一种提升代码可读性和开发效率的重要特性,已经成为语言设计的重要组成部分。Java作为一门成熟且广泛应用的编程语言,在其长期演进过程中,语法…...
567.字符串的排列
目录 一、题目二、思路2.1 解题思路2.2 代码尝试2.3 疑难问题 三、解法四、收获4.1 心得4.2 举一反三 一、题目 二、思路 2.1 解题思路 用两个哈希表比较来判断。s1的哈希表是否与s2相同。在窗口滑动过程中,用哈希表来维护。 2.2 代码尝试 class Solution { pub…...
DB2和mysql关于表和索引是否需要reorg的研究
DB2: DB2有个reorgchk的命令,是从SYSSTAT.TABLES和syscat.indexes这两个系统表中查表和索引的信息,并给出是否需要reorg表和索引的建议。 [db2inst1t3-ucm-ucm-rdb ~]$ db2 reorgchk CURRENT STATISTICS on table DB2ADMIN.ACAGENTTREE Ta…...
【Linux系统编程】:自旋锁,读写锁
文章目录 前言1. POSIX自旋锁1.1.定义自旋锁1.2.初始化1.3. 加锁1.4. 尝试加锁操作1.5. 解锁操作1.6. 销毁操作1.7.示例1.8.优缺点优点缺点 1.9.适用场景 2. 读写锁2.1 读写锁的工作原理2.2 读写模型2.3 常用接口2.3.1 定义锁并初始化2.3.2 申请读锁2.3.3 申请写锁2.3.4 解锁2.…...
位运算及常用技巧
涉及位运算的运算符如下表所示: 位运算的运算律: 负数的位运算 首先,我们要知道,在计算机中,运算是使用的二进制补码,而正数的补码是它本身,负数的补码则是符号位不变,其余按位取反…...
Chrome 浏览器:互联网时代的浏览利器
Chrome 浏览器:互联网时代的浏览利器 引言 在互联网时代,浏览器已经成为我们日常生活中不可或缺的工具。作为全球最受欢迎的浏览器之一,Chrome 浏览器凭借其出色的性能、丰富的扩展程序和简洁的界面,赢得了广大用户的喜爱。本文…...
web-文件上传-CTFHub
前言 在众多的CTF平台当中,作者认为CTFHub对于初学者来说,是入门平台的不二之选。CTFHub通过自己独特的技能树模块,可以帮助初学者来快速入门。具体请看官方介绍:CTFHub。 作者更新了CTFHub系列,希望小伙伴们多多支持…...
【react】react面试题
react面试题 对 React 的理解、特性 react18有哪些更新 JSX是什么 解释为什么浏览器不能读取jsx ReactNative中,如何解决8081端口被占用而提示无法访问的问题? React 生命周期 react事件机制 react 组件传值 React改变state的方式 re…...
逐笔成交逐笔委托Level2高频数据下载和分析:20250206
Level2逐笔成交逐笔委托数据分享下载 通过Level2逐笔成交和逐笔委托这种每一笔的毫秒级别的数据可以分析出很多有用的点,包括主力意图,虚假动作,让任何操作无所遁形。适合交易大师来分析主力规律,也适合人工智能领域的机器学习&a…...
__cvta_generic_to_shared
一 测试代码 #include <cuda_runtime.h> #include <cstdio> #include <cstdint>__global__ void test_cp_async(int* __restrict__ A,int* __restrict__ B){int tid = threadIdx.x;A[tid] = tid;__shared__ int smem[32];size_t smemAddr = __cvta_generic_…...
C++学习——缺省参数、重载函数、引用
目录 前言 一、缺省参数 1.1概念 1.2写法 1.3半缺省 1.4使用 二、重载函数 2.1.概念 2.2类型 2.3参数 2.4顺序 2.5问题 2.6原理 三、引用 1、引用是什么? 2、引用的使用方法 3、引用特性 1、引用在定义的时候必须要初始化 2、一个变量会有多个引用…...
docker-compose 配置nginx
前言 前端打包的dist文件在宿主机,nginx运行在docker-compose 问题 nginx.conf 在本地配置可以生效,但是链接到容器就报错 基于本地的nginx运行,本地nginx.conf 如下 server {listen 8081;location / {root /usr/local/software/testweb/…...
LQB(0)-python-基础知识
一、Python开发环境与基础知识 python解释器:用于解释python代码 方式: 1.直接安装python解释器 2.安装Anaconda管理python环境 python开发环境:用于编写python代码 1.vscode 2.pycharm # 3.安装Anaconda后可以使用网页版的jupyter n…...
【C语言】指针运算与数组关系:详细分析与实例讲解
博客主页: [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C语言 文章目录 💯前言💯1. 指针的基础运算1.1 指针的加减运算1.2 指针加整数与指针减整数1.3 指针与指针的运算 💯2. 指针的实际应用:模拟 strlen 函数2.1 使用指针模拟…...
C++数组
指针,是C数组工作方式的基础。 数组,基本上是元素的集合。按特定的顺序排列的一堆东西。 C数组,就是表示一堆的变量组成的集合。一般是一行相同类型的变量。 例子: #include <iostream> int main() {int example[5];exa…...
OSPF基础(2)
一、LSA的头部 LSA是OSPF的一个核心内容,如果没有LSA,OSPF是无法描述网络的拓扑结构及网段信息的,也无法传递路由信息,更加无法正常工作,在OSPFV2中,需要我们掌握的主要有6种。 LSA头部一共20byte,每个字段…...