洛谷 P1015 回文数

P1015 回文数

https://www.luogu.com.cn/problem/P1015 原题

很明显的高精度，(1999年竟然就考
主要有：高精度加法（含进位）、高精度判断回文数 以及可以把字符串转成数字数组

这道题还是很良心，只有16进制是陌生的，所以特判就好
而且数字长度只有100位，反正是很水的一道题了（虽然我被卡
要注意16进制里，A~F 是 10~15

对于字符串的读入还是要注意，题目中数字换了一行，所以注意不要读了换行

字符串的读入 https://www.cnblogs.com/wuwendongxi/p/13339796.html

主函数

int main(){
    cin>>n>>m;  //
    len=m.size();
    TurnIntoNumber();  // 字符串转数组的函数，可有可无，字符串还有各种函数更方便
    while(++cnt<=30){  // 记录目前转换次数
        int h=0;
        for(int i=0;i<len;i++){  // 高精度
            num2[i]=num[i]+num[len-i-1]+h;
            h=num2[i]/n;
            num2[i]%=n;
            if(i==len-1&&h!=0){  // 最后一位判断进位
                num2[len]=h,len++;
                h=0;
                break;
            }
        }
        if(IsPalindromicNumber(num2)==true){  // 判断回文数
            printf("STEP=%d",cnt);  // 如果可以直接输出
            return 0;
        }
        for(int i=0;i<len;i++)  // 换一下，这里用字符串更方便，有strcpy
            num[i]=num2[i];
        memset(num2,0,sizeof(num2));
    }
    printf("Impossible!");  // 不可以就impossible
    return 0;
}

判断回文数

bool IsPalindromicNumber(int k[]){
    for(int i=0;i<len/2;i++)
        if(k[i]!=k[len-i-1])
            return false;
    return true;
}

数字反转

因为高精度还是反着做比较好，于是需要反一下数字的顺序

这里又一次体现出string的好处，可以直接用reverse()
用数组做的话，只能通过下标控制了，需要找一下规律

void TurnIntoNumber(){
    for(int i=0;i<len;i++)
        if(n==16&&'A'<=m[len-i-1]&&m[len-i-1]<='Z')
            num[i]=m[len-i-1]-55;
        else
            num[i]=m[len-i-1]-48;
}

最后的完整代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n,len,cnt,num[109],num2[109];
string m;

bool IsPalindromicNumber(int k[]){
    for(int i=0;i<len/2;i++)
        if(k[i]!=k[len-i-1])
            return false;
    return true;
}

void TurnIntoNumber(){
    for(int i=0;i<len;i++)
        if(n==16&&'A'<=m[len-i-1]&&m[len-i-1]<='Z')
            num[i]=m[len-i-1]-55;
        else
            num[i]=m[len-i-1]-48;
}

int main(){
    freopen("1.txt","r",stdin);
    cin>>n>>m;
    len=m.size();
    TurnIntoNumber();
    while(++cnt<=30){
        int h=0;
        for(int i=0;i<len;i++){
            num2[i]=num[i]+num[len-i-1]+h;
            h=num2[i]/n;
            num2[i]%=n;
            if(i==len-1&&h!=0){
                num2[len]=h,len++;
                h=0;
                break;
            }
        }
        if(IsPalindromicNumber(num2)==true){
            printf("STEP=%d",cnt);
            return 0;
        }
        for(int i=0;i<len;i++)
            num[i]=num2[i];
        memset(num2,0,sizeof(num2));
    }
    printf("Impossible!");
    return 0;
}