1024 Palindromic Number
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 Kth step and K instead.
Sample Input 1:
67 3 • 1
Sample Output 1:
484 2
Sample Input 2:
69 3 • 1
Sample Output 2:
1353 3
题意
这道题是想要去获得一个回文数，例如 1234321 。
如果给定的数字不是回文数则需要将该数字加上它的逆序数，例如 123 不是回文数，则要加上它的逆序数 321 。然后再判断加上逆序数之后的数是否为回文数，如果还不是就重复上述操作直至是回文数为止。
但是有个条件限制，题目会给定 k 表示最多只能进行 k 次上述加法操作，如果 k 次加法结束还不是回文数，那就不管了直接输出。
最后需要输出最终得到的数字，以及通过了多少次上述的加法操作。
思路
这道题给定的数字很大，如果正常加法会爆 int ，需要用到高精度操作，所以一开始我们用字符串类型读入数字，然后再将字符串中的每一位都放进数组当中，注意要从字符转化回数字即 n[i] - '0' 。另外，我们数组中下标为 0 的位置存的是数字的最高位，例如 12345 放到数组中，下标从 0 到 4 存的是从 5 到 1 的数，即倒着放进数组，这样有利于我们后续的高精度操作。
先判断该数字是否为回文数，如果不是就进行上述的加法操作。另外，我们将数字反转利用了 c++ 的语法。
这里套用了高精度的加法模板，其中有些地方可以省略，因为这道题加法的两个数长度是相同的，所以可以不用同时判断 i 小于 a 和 b 的长度。另外，因为 t 是可能会有进位，所以需要判断 t 是否为 0 ,如果不为 0 还需要加到答案数组中。
判断得到的结果是否为回文数，如果已经是了就直接退出即可。另外，还需要记录进行了多少次加法操作。
输出最终结果。
代码
#include<bits/stdc++.h> using namespace std; //判断是否为回文数 bool check(vector<int> a) { for (int i = 0, j = a.size() - 1; i < j; i++, j--) if (a[i] != a[j]) return false; return true; } //高精度加法模板 vector<int> add(vector<int> a, vector<int> b) { vector<int> c; //这里要判断t是否为0，因为可能相加完后最后最高位仍然存在进位 for (int i = 0, t = 0; i < a.size() || i < b.size() || t; i++) { if (i < a.size()) t += a[i]; if (i < b.size()) t += b[i]; c.push_back(t % 10); t /= 10; } return c; } int main() { string n; int k; cin >> n >> k; //将数字用数组存起来，方便高精度操作 vector<int> a; for (int i = n.size() - 1; i >= 0; i--) a.push_back(n[i] - '0'); int cnt = 0; if (!check(a)) { while (k--) { cnt++; vector<int> b(a.rbegin(), a.rend()); //将数字反转 a = add(a, b); //高精度加法 if (check(a)) break; //判断是否是回文数 } } for (int i = a.size() - 1; i >= 0; i--) cout << a[i]; cout << endl << cnt << endl; return 0; }
