信息学奥赛一本通T1309-回文数-题解（C++代码）

解题思路:
1、逻辑铺垫：这个题目最重要的无非两个部分：①回文数判断②k进制高精度加法。

                      在读入输入数据的时候，我们可以把m当成字符串处理，从而简化了后面判断回文和高精度加法。

2、题目思路：步数最多30步，我们可以直接枚举步数，每次判断是不是回文数，如果是回文数直接输出步数并结束，如果不是回文数就需要做一个k进制的高精度加法（这里是一个整数+该整数反转之后的结果），重复上述步骤，直到步数大于30然后直接输出Impossible然后结束程序。

3、回文数判断比较简单，况且是字符串，只需枚举一边检查头尾是否相同即可；

     k进制高精度加法：首先需要把字符化的整数分别存到两个整型数组中（一个正序一个反序），然后进行相加即可，最后返回相加的结果。

两个k进制大整数相加的进位处理：

x = 0; // 进位
c = a + b + x; // 相加
x = c / k; // 产生的进位
c = c % k; // 取余之后的结果

注意事项:

1、注意16进制中不一定就是大写A~F，有一个测试数据就是小写的（我就因为这个一直90分，找不到原因~~~）。

2、注意步数是从0开始的哦~~

另外代码注释很详细了，有错有不懂欢迎留言~~谢谢！

参考代码:

#include <iostream>
using namespace std;
const int RN = 105;

int n;
string m; // 把第二整数m当作字符串处理 
char fuz[] = "0123456789ABCDEF"; // 辅助数组 

// 回文数判断 
bool judge(string s) {
	for (int i = 0, len = s.size(); i <= len / 2; ++i) // 判断到中间即可 
		if (s[i] != s[len - i - 1]) return false;
	return true;
}

// k进制高精度加法 
string add(int k, string s) {
	int a[RN], b[RN], c[RN];
	string res = "";
	int len = s.size(), lenc = 1, x = 0; // lenc-和数组的下标，x-进位
	for (int i = 0; i < len; ++i) { // 字符串转整数存入数组中 
		if (isdigit(s[i])) b[len - i] = s[i] - '0'; // 字符在0~9之间(比如10进制或者2进制) 
		else b[len - i] = toupper(s[i]) - 'A' + 10; // 字符在A~F或a~f之间（比如16进制） 
		a[i + 1] = b[len - i]; // 求和的另一个整数就是本身反转之后的整数	
	}
	while (lenc <= len) {
		c[lenc] = a[lenc] + b[lenc] + x; // 求和（不要忘记进位） 
		x = c[lenc] / k; // k进制d的进位 
		c[lenc++] %= k; // k进制进位之后的余数 
	} 
	if (x) c[lenc] = x; // 最后一次相加产生的进位 
	else lenc--; // 最后一次相加没有产生进位（lenc是预留位置）
	for (int i = lenc; i > 0; --i) res += fuz[c[i]]; // 重组字符串（注意进制不同对应的字符就不同） 
	return res; 
}

int main() {
	cin >> n >> m;
	for (int i = 0; i <= 30; ++i) {
		if (judge(m)) { // 如果是回文数输出步数 
			cout << i << endl;
			return 0; // 及时结束 
		} else m = add(n, m); // 反转相加 
	}
	cout << "Impossible" << endl; // 如果超过 30 步则输出 Impossible!
	return 0;
}