【NOIP】1999真题解析 luogu-P1015 回文数 | GESP四、五级以上可练习
NOIP 1999 普及组真题，主要考察字符串处理、高精度加法以及任意进制的进位规则。解题的核心是将数字看作字符串处理，在循环累加中验证回文特征。题目难度⭐⭐☆☆☆，洛谷难度等级普及−。
luogu-P1015 [NOIP 1999 普及组] 回文数
题目要求
题目描述
若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。
例如：给定一个十进制数 $56$，将 $56$ 加 $65$（即把 $56$ 从右向左读），得到 $121$ 是一个回文数。
又如：对于十进制数 $87$：
STEP1：$87+78=165$
STEP2：$165+561=726$
STEP3：$726+627=1353$
STEP4：$1353+3531=4884$在这里的一步是指进行了一次 $N$ 进制的加法，上例最少用了 $4$ 步得到回文数 $4884$。
写一个程序，给定一个 $N$（$2 \le N \le 10$ 或 $N=16$）进制数 $M$（$100$ 位之内），求最少经过几步可以得到回文数。如果在 $30$ 步以内（包含 $30$ 步）不可能得到回文数，则输出
Impossible!。
输入格式
两行，分别是 $N$，$M$。
输出格式
如果能在 $30$ 步以内得到回文数，输出格式形如
STEP=ans，其中 $\text{ans}$ 为最少得到回文数的步数。否则输出
Impossible!。
输入输出样例 #1
输入 #1
1
2
10
87
输出 #1
1
STEP=4
题目分析
这道题是一道结合了字符串处理、高精度计算和进制转换的经典模拟题。主要难点在于处理可能长达 100 位的超大整数及其 N 进制加法。
本题主要分为三个核心模块：
1. 回文数判断逻辑
判断一个数是否是回文数，最简单的方法是将其作为字符串存储。利用数组下标的特征，判断字符串的第 $i$ 位（str[i]）和与之倒数对应的位（str[str.length() - 1 - i]）字符是否一直保持相同。只要出现一对不相等的字符，就说明该串不是回文数。
2. N 进制的高精度加法运算
由于输入的 $M$ 可能长达 $100$ 位，远远超出了 C++ 中 long long 的存储范围。因此，我们必须使用高精度加法（大整数加法） 来完成累加操作。 对于两个字符串表示的数字，从后往前（即从个位开始向高位）逐位相加：
- 同位累加：取两个序列对应位置的数字相加，还要加上来自低位的进位。
- 进制规则：一般十进制加法是“逢十进一”，而在 N 进制加法中则是“逢 N 进一”。这就意味着，相加之和对 N 取余是留在该位的结果，除以 N 的商是向高位的进位值。
- 字符映射：要注意当数据进制为 $16$ 时，数字表示方式除了
0-9外，还可以用到A-F（或小写a-f）。因此在计算时我们需要实现两个工具函数来将其相互映射。char_to_int将字符转换为其代表的实际数学数值，而计算完成后，再通过int_to_char则将算得的值转回符号字符，存入字符串数组内。
3. 模拟求解流程
按照题目表述逐步模拟： 首先特判原输入字符串是否天生就是个回文串（如果是则经过 0 步就可以得到结果并退出）。如果不是，在一个上限为 30 次的循环内，进行下述操作：
- 反转当前的字符串（即题目说的从右向左读的数）。
- 让原数与反转后的数通过 N 进制高精度加法相加，得到新数。
- 判断新数是否成为回文，是的话就输出当前步数并结束程序；否则在下一次循环中将其视作新的“原数”继续推演。 若执行满 30 步后依然没有找到回文数，直接输出
Impossible!。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <algorithm>
#include <iostream>
// 字符转数字：支持 2~10 进制以及 16 进制的字符转化为对应的整数值
int char_to_int(char c) {
if (c >= '0' && c <= '9') return c - '0';
if (c >= 'A' && c <= 'F') return c - 'A' + 10;
if (c >= 'a' && c <= 'f') return c - 'a' + 10;
return 0;
}
// 数字转字符：将高精度计算产生的值（0~15）转化为对应的字符表示
char int_to_char(int v) {
if (v >= 0 && v <= 9) return '0' + v;
if (v >= 10 && v <= 15) return 'A' + (v - 10);
return '0';
}
// 检查给定的字符串是否为回文串
bool check(std::string str) {
for (int i = 0; i < str.length(); i++) {
// 双指针思想，判断首尾对应位置的字符是否相同
if (str[i] != str[str.length() - 1 - i]) {
return false; // 只要有一位不同，立刻返回不是回文串
}
}
return true;
}
// N 进制下的高精度加法运算
std::string big_sum(std::string str1, std::string str2, int n) {
std::string res = "";
int les = std::max(str1.length(), str2.length());
int carry = 0; // 进位标记
// 从个位（字符串的尾部）开始，遂位进行加法运算
for (int i = 0; i < les; i++) {
// 分别获取倒数第 i 位的值，如果超出了长度则记为 0
int v1 =
i < str1.length() ? char_to_int(str1[str1.length() - 1 - i]) : 0;
int v2 =
i < str2.length() ? char_to_int(str2[str2.length() - 1 - i]) : 0;
// 将对应位相加并带上进位
int tmp = v1 + v2 + carry;
res += int_to_char(tmp % n); // 取余 n 作为当前位的值，保存回字符串
carry = tmp / n; // 除以 n 计算向高位的进位
}
// 如果最高位计算完成后还有进位，需要额外补上
if (carry != 0) {
res += int_to_char(carry);
}
// 因为生成字符串是从低位逐步加到高位的字符，所以最终需要反转才是正确结果
std::reverse(res.begin(), res.end());
return res;
}
int main() {
int N;
std::string M;
std::cin >> N >> M; // 读取进制 N 和原始数值字符串 M
const int limit = 30; // 题目要求的最大步数限制
std::string str = M;
// 特判：如果初始状态就是一个回文数，则经过 0 步就可以得到
if (check(str)) {
std::cout << "STEP=0\n";
return 0;
}
// 最多进行 limit (30) 次加法尝试
for (int i = 1; i <= limit; i++) {
std::string tmp = str;
// 将原序列反转，得到从右向左读的数
std::reverse(tmp.begin(), tmp.end());
// 调用 N 进制的高精度加法
str = big_sum(str, tmp, N);
// 检查新生成的数字是否是回文数
if (check(str)) {
// 输出得到回文数字所需的步数，然后直接结束程序
std::cout << "STEP=" << i << "\n";
return 0;
}
}
// 超过 30 步仍未得到回文数，输出不可能
std::cout << "Impossible!\n";
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
