洛谷-P1015 回文数（进制转换+高精度加法）

题目描述

若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。

例如：给定一个十进制数5656，将5656加6565（即把5656从右向左读），得到121121是一个回文数。

又如：对于十进制数8787：

STEP1：8787+7878 = 165165 STEP2：165165+561561 = 726726 STEP3：726726+627627 = 13531353 STEP4：13531353+35313531 = 48844884

在这里的一步是指进行了一次NN进制的加法，上例最少用了44步得到回文数48844884。

写一个程序，给定一个NN(2 \le N \le 10,N=162≤N≤10,N=16)进制数MM(100100位之内)，求最少经过几步可以得到回文数。如果在3030步以内（包含3030步）不可能得到回文数，则输出Impossible!

输入格式

两行，分别是NN，MM。

输出格式

STEP=ans

输入输出样例

输入 #1

10
87

输出 #1

STEP=4

---

#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdlib>
#include <cstdio>

using namespace std;

int n = 105;
vector<int> num1(n), num2(n);

ostream & operator<<(ostream & os, vector<int> & v)
{
    int len = v[0];
    for (int i = len; i >= 1; --i)
        os << v[i];
    os << endl;
    return os;
}

char numToChar(int n)
{
    if (0 <= n && n <= 9) return '0' + n;
    return 'A' + (n - 10);
}

int charToNum(char ch)
{
    if ('0' <= ch && ch <= '9') return ch - '0';

    return 10 + (ch - 'A');
}

void init(vector<int> & v, string & s)
{
    int len = s.size();
    v[0] = len;
    for (int i = 1; i <= len; ++i)
        v[i] = charToNum(s[len - i]) - 0;
}

bool isPanlindrome(string & s)
{
    int len = s.size();
    int start = 0, end = len - 1;

    while (start <= end) {
        if (s[start++] != s[end--])
            return false;
    }
    return true;
}

bool check()
{
    string s;
    for (int i = num1[0]; i >= 1; --i) {
        s.push_back(numToChar(num1[i]));
    }

    if (isPanlindrome(s)) return true;

    return false;
}

void bigNumPlus(int base)
{
    int extra = 0;
    int pos = 1;
    while (pos <= num1[0] || pos <= num2[0]) {
        num1[pos] = num1[pos] + num2[pos] + extra;
        extra = num1[pos] / base;
        num1[pos] %= base;
        ++pos;
    }
    num1[pos] = extra;

    num1[0] = pos;
    while (num1[0] > 1 && num1[num1[0]] == 0) --num1[0];
}

void solve(int base, string & s)
{
    init(num1, s);

    int cnt = 0;
    while (cnt < 30) {
        ++cnt;
        num2 = num1;
        reverse(num2.begin() + 1, num2.begin() + 1 + num2[0]);
        bigNumPlus(base); //结果保存在num1中
        if (check()) {
            cout << "STEP=" << cnt << endl;
            return;
        }
    }
    cout << "Impossible!" << endl;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int base;
    string s;
    cin >> base >> s;

    solve(base, s);

    return 0;
}

这道题虽然看似代码很长，其实就是按照思路逐个完善函数就可以了，核心两个，一个是大数加法，一个是进制转换，这道题目因为只涉及16进制和10以内的进制转换，只需要额外写两个转换函数。