题目描述
波浪数是在一对数字之间交替转换的数，如1212121，双重波浪数则是指在两种进制下都是波浪数的数，如十进制数191919是一个十进制下的波浪数，它对应的十一进制数121212也是一个波浪数，所以十进制数191919是一个双重波浪数。
类似的可以定义三重波浪数，三重波浪数在三种不同的进制中都是波浪数，甚至还有四重波浪数，如十进制300=606（七进制）=363（九进制）=454（八进制）=1A1（十三进制）…，你的任务就是在指定范围内找出双重、三重、四重波浪数。
输入输出格式
输入格式：
单独一行包含五个用空格隔开的十进制整数，前两个数表示进制的范围（2••32），第三与第四个数表示指定的范围（1••10000000），第五个数为2,3,4中的一个，表示要找的波浪数的重数。
输出格式：
从小到大以十进制形式输出指定范围内的指定重数的波浪数。一行输出一个数。
输入输出样例
输入样例#1：
10 11 190000 960000 2
输出样例#1：
191919 383838 575757 767676 959595
题解：
如果直接暴力枚举的话时间上承受不了，我们可以直接构造波浪数，所以只需要枚举位数，重复出现的两个数字，和波浪数的长度。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> const int maxn=10000000+1; using namespace std; int l1,l2,r1,r2,num,mxl,mnl; int cnt[maxn]; int h(int a,int b,int k,int len) {//构造a,b在k进制下长度为len的波浪数 int x=0; for(int i=1;i<=len;i++) { if(i&1) x=x*k+a;//(i&1)等于(i%2) else x=x*k+b; } return x; } int clen(int x,int k) {//求x在k进制下的长度 int cnt=0; while(x) { x=x/k; cnt++; } return cnt; } int main() { scanf("%d%d%d%d%d",&l1,&r1,&l2,&r2,&num); for(int k=l1;k<=r1;k++) for(int i=1;i<k;i++)//这儿一定要从1开始，首位不能是0 for(int j=0;j<k;j++) if(i!=j) { mnl=clen(l2,k);mxl=clen(r2,k); for(int l=mnl;l<=mxl;l++) { int tmp=h(i,j,k,l); if(tmp>=l2&&tmp<=r2)//这儿一定要加的，万一构造出来的数超出了数组的范围呢？ cnt[tmp]++; } } for(int i=l2;i<=r2;i++) if(cnt[i]==num) printf("%d ",i); return 0; }