P1112 波浪数【洛谷算法习题】

P1112 波浪数网页链接P1112 波浪数题目描述波浪数是在一对不同数字之间交替转换的数如1212121 12121211212121双重波浪数则是指在两种进制下都是波浪数的数如十进制数191919 191919191919是一个十进制下的波浪数它对应的十一进制数121212 121212121212也是一个波浪数所以十进制数191919 191919191919是一个双重波浪数。特别地只有一位的数也算作波浪数例如1 11。类似的可以定义三重波浪数三重波浪数在三种不同的进制中都是波浪数甚至还有四重波浪数如300 ( 10 ) 606 ( 7 ) 363 ( 9 ) 454 ( 8 ) 1 A 1 ( 13 ) 300_{(10)}606_{(7)}363_{(9)}454_{(8)}1\mathtt{A}1_{(13)}300(10)​606(7)​363(9)​454(8)​1A1(13)​下标表示采用的进制。你的任务就是在指定范围内找出双重、三重、四重波浪数。输入格式单独一行包含五个用空格隔开的十进制整数l , r , L , R , k l, r, L, R, kl,r,L,R,k。[ l , r ] [l, r][l,r]表示应当考虑的进制的范围[ L , R ] [L,R][L,R]表示应当考虑的数字的范围k kk表示你应该找的波浪数的重数。输出格式从小到大以十进制形式输出指定范围内的指定重数的波浪数。一行输出一个数。输入输出样例 #1输入 #110 11 190000 960000 2输出 #1191919 383838 575757 767676 959595说明/提示数据范围及约定对于全部数据保证2 ≤ l ≤ r ≤ 32 2\le l\le r\le 322≤l≤r≤321 ≤ L ≤ R ≤ 10 7 1\le L\le R\le 10^71≤L≤R≤107k ∈ { 2 , 3 , 4 } k\in \{2, 3, 4\}k∈{2,3,4}。解题思路本题核心是反向构造波浪数哈希计数高效解决k重波浪数的求解问题。直接枚举数字判断是否为波浪数效率极低因此采用构造法枚举[l,r]内的所有进制对每个进制枚举两组不同数字交替拼接生成该进制下所有不超过R的波浪数用数组统计每个数字满足条件的进制数量。构造完成后遍历数值区间[L,R]筛选出计数恰好等于k的数字并按序输出。该方法用构造替代遍历判断极大降低计算量完美适配R≤10⁷、进制范围≤32的题目约束高效且精准。总结核心逻辑反向构造各进制下的波浪数统计每个数字符合的进制数量筛选出恰好k重的结果。关键操作枚举进制与数字对生成波浪数数组计数遍历区间输出符合要求的数字。效率保障构造法无冗余计算完美适配题目最大数据范围运行效率极高。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e710;constll p1e97;constll INF1e18;constll M5e310;ll a[40],b[N];voidfind(ll x,ll r){ll lt,t;for(ll i1;ix;i)for(ll j0;jx;j)if(i!j){lt0;t0;while(tr){lt;if(lt%20)a[lt]i;elsea[lt]j;tt*xa[lt];if(tr)break;b[t];}}}intmain(){ll jl,jr,l,r,k;cinjljrlrk;for(ll ijl;ijr;i)find(i,r);for(ll il;ir;i){if(b[i]k)coutiendl;}return0;}