题解 P1143 【进制转换】

· · 题解

update：

修改了一些语焉不详之处 19/11/16

新加了几个坑空 19/11/16（没错就是CSP2019的day1）

话说你们为什么都非要先转十进制啊！！！

还要用什么快速幂的说……

我鈦蒟蒻，不会怎么办啊QAQ

今天来教大家读入优化~~

不要急，往下看，正解很简单❤

首先假设我们都知道，getchar()明显快于scanf(),所以常常有人用这个来 卡常数 压时间

读入一个整数的方法：

inline int read(int &x)
{
    x=0;
    int f=1;
    char c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') x*=10,x+=c-'0',c=getchar();
    x*=f;
}//读完后，是数字的下一个字符
//这是一种任意十进制快速读法

而那种十进制读入法是可以优化的

优化方法如下

inline int read()
{
    int x=0;
    char c=getchar();
    while(c<48||c>47)//c<'0'||c>'9'
        c=getchar();
    while(c>47&&c<58) x*=10,x+=c-48,c=getchar()
    return x;
}//仅能读正整数

亲测read()比scanf()快大约5倍

那么大家想一想,如果n=10，题目中输入时

第二行不就是read()吗？！

那么问题来了，怎么从十进制读入变成n进制读入呢？

相信聪明的你一定想到了办法 :-)

我们在读入优化时(假设你已经会了读入优化……)是按位读的(十进制位)

然后我们只需按位读(n进制位)

注意别忘了特判'A'~'F'

所以可以这样写(读入)

#include<cstdio>
int n;
inline int isint(char c)//可将'0'~'9'及'A'~'F'转化成如题所示数字并将非数字字符返回-1注意此时c并不会被修改
{
    if(c>='A'&&c<='F')
        return c-55;//'A'=65,10=10;
    if(c>47&&c<58)
        return c-48;
    return -1;
}
inline void read(int &x)
{
    char c=getchar();
    while(isint(c)==-1) c=getchar();
    while(~isint(c)/*判断是不是数*/) x*=n,x+=isint(c),c=getchar();
}//read()后会读到数字后的第一个字符(读完)

好的本题前两行输入完成❤

现在你手里有一个以int表示的n进制数x

其实输出也能优化

常规 卡常 压时间技巧如下

void otp(int k)
{
    if(!k) return;
    otp(k/10);
    putchar(k+48);
}

其实这已经很好了(当然也不是不能改)

假设你前面已经全明白了(不明白请回头深造)

输出优化也可以被方便的转成m进制

方法如下

int m;
inline char cic(int x)//change into char 意在将一个n进制数的某位转成对应的m进制
{
    if(x<10)//毕竟不会出负数，算个小优化~
        return x+48;
    return x-10+'A';
}
void otp(int k)
{
    if(!k) return;
    otp(k/m);
    putchar(cic(k%m));
}

以下是题解

创建和邪落谷，警惕陶片放逐

为了您和他人的安全，请勿抄标程

(直接粘贴标程并提交有惊喜呦~~)

#include<cstdio>
int n,x,m;
inline int isint(char c)
{
    if(c>='A'&&c<='F')
        return c-55;
    if(c>47&&c<58)
        return c-48;
    return -1;
}
inline int read()
{
    int x=0;
    while(~isint(c)) x*=n,x+=isint(c),c=getchar();
    return x;
}
inline char cic(int x){
    if(x<10)
        return x+48;
    return x-10+'A';
}
void otp(int k)
{
    if(!k) return;
    otp(k/m);
    putchar(cic(k%m));
}
int main()
{
    scanf("%d",&n);
    x=read();
    scanf("%d",&m);
    otp(x);
    putchar('\n');
}

希望能帮助到大家，谢dalao们观看，欢迎来喷呦