PAT A1024 Palindromic Number(25)[回文数，高精度]

A number that will be the same when it is written forwards or backwards is known as a Palindromic Number. For example, 1234321 is a palindromic number. All single digit numbers are palindromic numbers.

Non-palindromic numbers can be paired with palindromic ones via a series of operations. First, the non-palindromic number is reversed and the result is added to the original number. If the result is not a palindromic number, this is repeated until it gives a palindromic number. For example, if we start from 67, we can obtain a palindromic number in 2 steps: 67 + 76 = 143, and 143 + 341 = 484.

Given any positive integer $N$, you are supposed to find its paired palindromic number and the number of steps taken to find it.

Input Specification:

Each input file contains one test case. Each case consists of two positive numbers $N$ and $K$, where $N$ (≤1010) is the initial numer and $K$ (≤100) is the maximum number of steps. The numbers are separated by a space.

Output Specification:

For each test case, output two numbers, one in each line. The first number is the paired palindromic number of $N$, and the second number is the number of steps taken to find the palindromic number. If the palindromic number is not found after $K$ steps, just output the number obtained at the $K$ th step and $K$ instead.

Sample Input 1:

67 3

Sample Output 1:

484
2

Sample Input 2:

69 3 

Sample Output 2:

1353
3

题意

判断一个大整数$N$是不是回文数，若不是，判断 $N$ + $N$ 反转之后的结果是不是回文数，直到最后结果为为回文数或者次数到达限制

思路1

1. 大整数加法，直接套模板
2. 判断回文首尾双指针

代码1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool check(const vector<int> &v)
{
    for(int i = 0, j = v.size() - 1; i < j; i++, j--)
        if(v[i] != v[j])
            return false;
    return true;
}

vector<int> add(vector<int> &a, vector<int> &b)
{
    vector<int> ans;
    int t = 0;
    for(int i = 0; i < a.size() || i < b.size(); i++ )
    {
        if(i < a.size())  t += a[i];
        if(i < b.size())  t += b[i];
        ans.push_back(t % 10);
        t /= 10;
    }
    if(t)
        ans.push_back(t);
    return ans;
}

int main()
{
    string str;
    int k;
    cin >> str >> k;
    vector<int> a;
    for(int i = str.size() - 1; i >= 0; i--)
        a.push_back(str[i] - '0');

    int cnt = 0;
    for( ; cnt < k; cnt++)
    {
        if(check(a))
            break;
        vector<int> b(a.rbegin(), a.rend());
        a = add(a, b);
    }
    for(int i = a.size() - 1; i >= 0; i--)
        printf("%d", a[i]);
    printf("\n%d\n", cnt);
    return 0;
}