首页/新闻资讯/正文详情

波浪数算法解析与高效实现

发布时间:2026/11/6 2:21:11 来源:云帆数科 栏目:资讯中心
波浪数算法解析与高效实现
1. 波浪数问题解析与算法实现第一次在洛谷刷到P1112波浪数这道题时我也被题目描述绕晕了。题目要求我们找出在给定区间[l,r]内恰好有c种进制表示是波浪数的所有整数。所谓波浪数指的是在某个进制下数字的各位交替出现两个不同数字的数比如十进制下的121、1313等。1.1 波浪数的数学定义波浪数在数学上可以严格定义为对于一个k进制的n位数d1d2...dn如果满足d1≠d2且对于所有1≤i≤n-2都有didi2那么这个数就是k进制下的波浪数。例如十进制中121交替数字1和2八进制中363交替数字3和6十六进制中AFA交替数字A和F这种数的特殊之处在于同一个数值在不同进制下可能呈现出完全不同的波浪特性。比如十进制数10二进制1010波浪数交替1和0三进制101波浪数交替1和0十进制10不是波浪数1.2 问题重述与输入输出题目给出的完整输入格式是五个整数a,b,l,r,ca和b表示进制范围的下限和上限a≤k≤bl和r表示数值范围的下限和上限l≤x≤rc表示需要的波浪数表示方式的数量输出则是在[l,r]范围内恰好有c种进制在a到b范围内下是波浪数的所有整数每行一个。2. 算法设计与优化思路2.1 暴力法的局限性最直观的想法是对[l,r]范围内的每个数x枚举a到b的每个进制k检查x在k进制下是否是波浪数。这种方法虽然直接但效率极低。假设l1, r1e7a2, b36那么时间复杂度将达到O((r-l1)*(b-a1)*log(r))对于较大的r值根本无法承受。2.2 逆向思维生成所有可能的波浪数更聪明的做法是反过来思考不是检查每个数是否是波浪数而是主动生成所有在a到b进制下可能的波浪数然后统计每个数被生成了多少次。这种方法的核心优势在于波浪数的生成有明确的模式可以高效枚举避免了大量无效的进制转换和检查统计过程可以通过简单的数组计数完成具体来说对于每个进制ka≤k≤b我们生成所有k进制下的波浪数然后对于生成的每个数x如果x在[l,r]范围内就在计数数组v[x]上加1。最后我们只需要输出所有满足v[x]c的x即可。2.3 波浪数的生成算法生成k进制下的波浪数需要仔细考虑以下几点波浪数由两个不同的数字交替组成如abab...或baba...波浪数可以有任意长度但必须至少两位首位不能为0在大多数进制中具体生成步骤如下枚举第一个数字i1到k-1枚举第二个数字j0到k-1且j≠i交替使用i和j构建数字直到超过r例如在十进制下生成波浪数选择i1,j2生成12,121,1212,...选择i2,j1生成21,212,2121,...3. 代码实现与细节处理3.1 核心代码解析基于上述思路我们可以实现如下C代码#includebits/stdc.h using namespace std; int a,b,l,r,c,t,x; int v[10000005]; // 存储重数 int main(){ memset(v,0,sizeof(v)); scanf(%d%d%d%d%d,a,b,l,r,c); // 枚举所有可能的进制 for(int ka; kb; k){ // 枚举第一个数字i1到k-1 for(int i1; ik; i){ // 枚举第二个数字j0到k-1且j≠i for(int j0; jk; j){ if(i ! j){ // 确保两个数字不同 x 0; t 0; // 用于交替选择i和j while(x r){ if(t%2 0){ x x*k i; // 添加i } else { x x*k j; // 添加j } t; // 如果x在范围内计数加1 if(x l x r) v[x]; } } } } } // 输出结果 for(int il; ir; i){ if(v[i] c) printf(%d\n,i); } return 0; }3.2 关键细节说明数组大小v数组需要足够大以覆盖r的最大值。题目中r≤1e7所以声明为1e75是安全的。进制转换技巧代码中使用x x*k digit的方式直接在十进制下构建k进制数的值避免了显式的进制转换。交替模式实现使用变量t的奇偶性来决定当前应该添加i还是j简洁高效。边界处理while循环的条件是x≤r确保不会生成超出范围的数内层if检查x是否在[l,r]范围内。去重处理同一个数x可能被不同进制下的波浪数生成多次v[x]会自动累加这些情况。3.3 复杂度分析该算法的时间复杂度主要取决于波浪数的生成数量。对于每个进制k生成的波浪数数量大约为O((k^2)*logk(r))。由于k≤b且r≤1e7实际运行效率很高能够在题目要求的时间内完成。空间复杂度为O(r)主要用于存储计数数组v。4. 优化与扩展思考4.1 性能优化技巧提前终止当x超过r时立即终止当前波浪数的生成避免不必要的计算。并行处理不同进制k的波浪数生成是完全独立的可以考虑多线程并行处理。内存优化如果r非常大可以使用哈希表或稀疏数组来替代全范围的计数数组。4.2 常见错误与调试数组越界确保v数组足够大否则会导致运行时错误。整数溢出在构建x的过程中可能会超出int范围对于更大的r值应该使用long long。边界条件特别注意l1和r1e7时的特殊情况。进制范围确保a≥2且b≥a否则可能出现无效输入。4.3 算法扩展这个问题可以扩展为更一般的形式多波浪数允许三个或更多数字的交替模式。更大范围使用更高效的数据结构处理更大的数值范围。动态查询支持多次查询不同的c值而不需要重新计算。5. 实际应用与变种波浪数的概念虽然看似简单但在实际中有一些有趣的应用数字艺术波浪数因其规律的模式常被用于数字艺术和图形设计。密码学某些加密算法会利用数字的特定模式来生成密钥。数学教育帮助学生理解进制转换和数字模式的良好示例。类似的编程题目变种包括寻找特定模式的数字如回文数多进制下的数字特性判断数字模式的统计与分类提示在解决这类问题时逆向思维往往能带来意想不到的优化效果。与其被动检查每个数是否满足条件不如主动生成所有可能的解并统计。

相关推荐

工程机械短视频创作指南与中联土方挑战赛解析
工程机械短视频创作指南与中联土方挑战赛解析

1. 项目背景与赛事定位"中联土方全民抖音挑战赛"是一场面向大众的短视频创作赛事,由工程机械行业龙头企业中联重科旗下土方机械公司发起。赛事以20万元高额奖金作为核心吸引力,旨在通过抖音平台的流量优势,实现品牌曝光、产品推广与… · 2026/11/6 2:21:10

ponytail插件怎么用?从安装配置到进阶技巧的完整指南
ponytail插件怎么用?从安装配置到进阶技巧的完整指南

1. 从“ponytail”这个热搜词说起:它到底指什么 第一次看到“ponytail”冲上热搜的时候,我下意识以为是某个发型教程火了。马尾辫嘛,谁不会扎。但点进去翻了翻相关讨论,才发现事情没那么简单——热搜里跟着的是“ponytail skill”… · 2026/11/6 1:33:15

Python卫星轨道数据解析与可视化:TLE、SGP4与星下点轨迹实战
Python卫星轨道数据解析与可视化:TLE、SGP4与星下点轨迹实战

卫星轨道数据解析与可视化这件事,我从第一次接触到现在差不多有三年多时间了。最开始是因为一个做航天科普的朋友找我帮忙,说想做一个能实时展示在轨卫星位置的小工具,让观众能直观看到“头顶上到底飞着哪些东西”。当时我第一反应是这玩意儿… · 2026/10/31 17:00:34

Photoshop插件生态:技术民主化与效率革命
Photoshop插件生态:技术民主化与效率革命

1. 项目概述:Photoshop插件生态与效率革命在数字创意领域,Photoshop早已超越单纯的图像处理软件,成为连接创意与技术的生态系统。根据Adobe官方数据,全球超过90%的专业设计师在日常工作中依赖PS插件提升效率。这个2300款插件合集包… · 2026/11/6 2:20:52

工业组态网关在跨区域监控中的应用与优化
工业组态网关在跨区域监控中的应用与优化

1. 工业组态网关在跨区域监控中的核心价值在制造业数字化转型浪潮中,实现分散站点的集中监控一直是痛点问题。去年我们为某化工集团实施的跨省监控项目就面临类似挑战——三个生产基地分别位于不同省份,各自采用独立的控制系统,数据孤岛现象严… · 2026/11/6 2:20:52

2026百元半入耳蓝牙耳机选购指南与技术解析
2026百元半入耳蓝牙耳机选购指南与技术解析

1. 百元级半入耳式蓝牙耳机的市场现状2026年的音频设备市场正在经历一场"技术下沉"的革命。曾经只出现在中高端产品的蓝牙5.3芯片、自适应降噪算法等配置,如今已经渗透到百元价位段。作为日常通勤和轻度娱乐的主力设备,半入耳式结构因其舒适性… · 2026/11/6 2:20:52

Photoshop插件合集:提升设计效率的终极指南
Photoshop插件合集:提升设计效率的终极指南

1. 项目概述:PS插件生态与效率革命在数字创意领域,Photoshop早已超越单纯的图像处理软件范畴,演变为一个庞大的生态系统。根据Adobe官方数据,全球PS用户中超过78%会定期使用第三方插件提升工作效率,而专业设计师平均每… · 2026/11/6 2:20:52

半导体良率分析的多源数据集成技术与应用
半导体良率分析的多源数据集成技术与应用

1. 半导体良率分析的痛点与数据集成价值在半导体制造领域,良率(Yield)是衡量生产质量的核心指标。一条12英寸晶圆产线每天产生的数据量可达TB级别,这些数据分散在MES(制造执行系统)、EAP(设备自… · 2026/11/6 2:20:52

Rime小狼毫五笔配置:安装、码表、词库与部署排查
Rime小狼毫五笔配置:安装、码表、词库与部署排查

简介:面向五笔输入法爱好者的Rime小狼毫整合包,基于小狼毫平台封装长期自用的高级五笔词库,词库经二十余年维护与优化,并针对多数人的打字习惯预调好配置,适合希望减少折腾、直接获得稳定五笔方案的中高级用户&#xf… · 2026/11/6 2:19:52

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:27:59

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:03

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:07

三菱PLC数据采集到数据库的时序设计:Python+MC协议实战
三菱PLC数据采集到数据库的时序设计:Python+MC协议实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/6 1:02:11

ASIC主模式RTL设计:状态机与三态驱动的流片级实现
ASIC主模式RTL设计:状态机与三态驱动的流片级实现

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/6 1:02:11

STM32嵌入式C++开发:GDB调试与Renode仿真实战指南
STM32嵌入式C++开发:GDB调试与Renode仿真实战指南

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/6 1:02:11

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:27:59

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:03

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:07

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码