P1112 波浪数

2018-06-17 22:16:21来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

 

题目描述

波浪数是在一对数字之间交替转换的数,如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\n",i);
    return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:P3805 【模版】manacher算法

下一篇:2147 数星星