2025年【江苏“信息与未来”编程思维】真题及题解T1幸运数字题目描述如果一个n nn位正整数恰好由数字0 , 1 , 2 , ⋯ , n − 1 0, 1, 2, \cdots , n - 10,1,2,⋯,n−1组成Dr. X 就称它为“幸运数字”例如1023 10231023是一个幸运数字因为它是一个四位数且恰好由数字0 , 1 , 2 , 3 0, 1, 2, 30,1,2,3组成。123 123123不是幸运数字因为三位幸运数字应该由数字0 , 1 , 2 0, 1, 20,1,2组成。012 012012不是幸运数字因为我们只考虑不含前导零的正整数。现在给定两个正整数a aa和b bb请你计算a , a 1 , a 2 , ⋯ , b a, a 1, a 2, \cdots, ba,a1,a2,⋯,b中幸运数字的数量。输入格式输入两个空格分隔的正整数a aa和b bb。输出格式输出一个整数表示a , a 1 , a 2 , ⋯ , b a, a 1, a 2, \cdots, ba,a1,a2,⋯,b中幸运数字的数量。输入输出样例 1输入 14 202输出 14输入输出样例 2输入 21 100000输出 2119说明/提示样例1 \textbf 11解释在4 44和202 202202之间幸运数字有10 , 102 , 120 , 201 10, 102, 120, 20110,102,120,201。数据范围对于100 % 100\%100%的数据满足1 ≤ a ≤ b ≤ 10 6 1 ≤ a ≤ b ≤ 10^61≤a≤b≤106。思路分析幸运数字的定义对于一个n位的正整数它必须恰好由数字0, 1, 2, …, n-1各出现一次组成且不能包含其他数字。例如10234位由0,1,2,3各一次是幸运数字1233位缺少0且包含3不是。判断方法求出位数n并用计数数组c[10]记录每个数字0~9出现的次数。检查数字0到n-1是否都恰好出现一次。因为总位数恰好为n如果0~n-1各出现一次则位数已经占满不可能再出现其他数字。满足则返回true否则返回false。区间长度最大为10 6 10^6106每个数最多 7 位暴力枚举判断足够高效。代码实现#includebits/stdc.husingnamespacestd;inta,b;// 区间左右端点boolcheck(intx){// 判断x0是否为幸运数字intn0,c[10]{0};// n:位数, t:临时副本, c:数字计数while(x0){// 逐位分解c[x%10];// 统计该数字出现次数x/10;n;// 位数累加}for(inti0;in;i){// 检查0~n-1是否都恰好出现一次if(c[i]!1)returnfalse;// 不满足则不是幸运数字}returntrue;// 全部满足是幸运数字}intmain(){cinab;ints0;// 计数器for(intia;ib;i){// 遍历区间内所有整数if(check(i))s;// 是幸运数字则累加}couts;return0;}功能分析核心函数check通过统计数字出现次数并验证0到位数-1是否各出现一次高效判断一个数是否为幸运数字。由于位数有限≤7数组c大小固定为 10时间开销极小。主函数逻辑读取区间[a,b]枚举每个整数调用check累加合法个数最后输出答案。复杂度时间复杂度 O((b-a1) · log₁₀ b)最坏约 10⁶ × 7 次操作可在 1 秒内完成。空间复杂度 O(1)仅使用常数大小的数组。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}