1024. Palindromic Number.md

【PAT A-1024】Palindromic Number

题意概述

非回文数可以通过一系列操作变成回文数。首先，将非回文数反转，然后与原始数相加。如果和不是回文数，则对和重复此操作直到和是回文数。例如，如果我们从 67 开始，则可以分两步获得回文数：67 + 76 = 143，以及 143 + 341 = 484。给定任何正整数 N，您应该找到它变成的回文数和变成这个回文数所需的步骤数。

输入输出格式

输入由两个正整数 N 和 K 组成，其中是初始数字，K 是最大步骤数。这些数字用空格分隔。

输出两个数字，每行一个。第一个数字是能够变成的回文数，第二个数字是变成这个回文数所需的步骤数。如果在 K 步后未找到回文数，则只需输出在 K 步获得的数，然后输出 K。

数据规模

$$N\le{10}^{10},K\le 100$$

算法设计

由于$N\le{10}^{10}$，且最多要进行 100 次这样的加法，用 long long 也是存储不下的，最好用 string 存储，进行大整数加法运算。然后按步模拟即可。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
string Plus(const string& a, const string& b) {
    string ans;
    gg carry = 0;  //进位
    for (gg i = a.size() - 1, j = b.size() - 1; i >= 0 or j >= 0 or carry != 0; --i, --j) {
        gg p1 = i >= 0 ? a[i] - '0' : 0, p2 = j >= 0 ? b[j] - '0' : 0;
        gg k = p1 + p2 + carry;
        ans.push_back(k % 10 + '0');
        carry = k / 10;
    }
    reverse(ans.begin(), ans.end());  //要进行翻转
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ki, step = 0;
    string ni;
    cin >> ni >> ki;
    for (; step < ki and not equal(ni.begin(), ni.end(), ni.rbegin()); ++step) {
        string a = ni;
        reverse(a.begin(), a.end());
        ni = Plus(ni, a);
    }
    cout << ni << "\n" << step;
    return 0;
}