看到题目名里的“回文数”可能有人觉得这题简单不就是判断一个数字正着读反着读一样吗但等你真打开洛谷P1015或者信息学奥赛一本通1309看到题目给的进制可以是2到16数字最长能到100位还要在30步内反复做“原数加倒序数”的操作才会意识到这道NOIP1999普及组老题真正想考的是三件事进制转换、高精度加法、回文串判断。我第一次做这道题时也犯过“觉得简单”的毛病用long long存数字样例倒是过了一提交就WA。后来老老实实改成字符串模拟才把题目吃透。这篇文章就把我的完整思路、参考代码、踩坑经历都写出来适合刚接触高精度的入门选手也适合准备NOIP普及组复赛、想系统过一遍字符串模拟加法的人。1. 先别急着写代码题目里的三个关键词1.1 这道题和“普通回文数”有什么不同普通回文数题一般只让你判断一个十进制整数是不是回文数写个反转比一比就结束。P1015不是这种玩法它给了你一个N进制数MN可以是2到10也可能是16。这意味着输入里可能出现大写字母A到F而且每一步加法都必须遵守N进制的进位规则不能按十进制算完再转回去。举个例子N16时M5它的倒序数还是5相加得到A十进制10吗不是5510在十六进制里写作A这没问题。但如果MA倒序还是AAA20十六进制也就是十进制32。如果按十进制算101020然后把20转成十六进制也是14等等这里很容易乱。正因为容易乱所以正确的做法是全程在N进制字符串上操作不要中途转到十进制。还有个麻烦点M的长度最长可以到100位。100位的十进制数本身已经远超long long范围更不用说N16时每一位还是字符。这也是为什么这道题必须走高精度路线。1.2 30步是怎么来的题目要求如果在30步以内含30步得到一个回文数就输出STEP步数否则输出Impossible!。这个30步不是随便写的。每做一次“原数加倒序数”结果最多比原来多一位因为高精度加法里最高位进位最多是1。假设初始M有100位30步之后最多130位。用字符串模拟每次加法复杂度O(L)判断回文也是O(L)总复杂度O(30L)非常稳定。这个“数据规模提示算法”的思路在竞赛题里很常见看到30步、100位这类数字就该想到不是让你暴力用整数类型硬扛。顺便说一个背景知识十进制下有个著名的“196问题”指的是某些数反复加上它的倒序数目前也不确定最终能不能得到回文数。竞赛题把步数限制在30相当于给了确定的终止条件所以输出Impossible!并不是bug而是题目设计的一部分。1.3 先自己推一遍样例题面给的样例通常是N10M87输出STEP4。我们手动推一遍87 78 165不是回文165 561 726不是回文726 627 1353不是回文1353 3531 4884是回文所以答案是4。这个手推过程能帮你避开一个常见误解题目说的“把这个数加上它的倒序数”不是把字符串拼在一起。比如165 561个位516十位6612十位要进位所以结果是726而不是“165561”。真正的竖式加法必须处理进位。2. 高精度加法为什么必须写成字符串模拟2.1 从long long溢出说起初学者最容易犯的错就是把输入的数字转成long long然后循环相加和判断。如果M只有两三位这个做法能过样例但正式数据一上去就WA。原因很简单100位的数字long long根本存不下而且每次相加位数还在变化30步之后最长130位用C的整数类型毫无机会。所以正解是字符串模拟手算竖式。这也是信息学竞赛“高精度”知识点的标准套路把大数按位拆开逐位相加逢N进一。用string存的好处是长度不固定动态变化时不需要手动扩容。如果你刚学高精度用vector存数字也可以但string在本题里写起来更顺手。2.2 竖式加法的核心逻辑假设有两个字符串a和b表示两个N进制数。它们的长度一定相同因为b是a的倒序。从右往左逐位处理取出a当前位和b当前位转成整数加上上一位的进位carry当前位的结果是sum % N新的进位是sum / N。因为N进制下两个一位数相加再加上一个进位sum最大是(N-1)(N-1)12N-1所以carry只会是0或1。这个结论能帮你理解但代码里写成通用的sum / base最稳妥以后遇到任意进制也不用改。举例十进制8778个位7815写5进1十位87116写6进1最高位进位1写到最前面得到165。如果最高位有进位千万别丢掉。很多人写循环时条件写成while (i 0 || j 0)两个字符串都扫描完就退出导致最后的carry没处理直接WA。2.3 为什么逆序数就是原串反转题目说“把这个数加上它的倒序数”倒序数就是原字符串的反转。比如M1234倒序数就是4321。字符串反转在C里可以直接用reverse(s.begin(), s.end())Python里用s[::-1]。但这里有个隐蔽问题反转操作会改变原字符串。C的reverse是原地反转Python的切片反转不会改变原串。如果你在判断回文时直接对原串reverse下一步做加法时原串已经被改成倒序了算出来的结果就会出错。正确做法是先把原串复制一份再对副本反转。这个“拷贝后再反转”的习惯能帮你避开大量字符串题目的坑。3. 完整代码与逐段讲解3.1 C参考实现我直接给出一份能过的C代码代码风格偏竞赛注释写在关键位置#include bits/stdc.h using namespace std; int N; string M; int val(char c) { if (c 0 c 9) return c - 0; return c - A 10; } char toChar(int x) { if (x 10) return char(0 x); return char(A x - 10); } string add(string a, string b) { string res; int carry 0; int i a.size() - 1, j b.size() - 1; while (i 0 || j 0 || carry) { int sum carry; if (i 0) sum val(a[i--]); if (j 0) sum val(b[j--]); res.push_back(toChar(sum % N)); carry sum / N; } reverse(res.begin(), res.end()); return res; } bool isPal(const string s) { string r s; reverse(r.begin(), r.end()); return s r; } int main() { cin N M; for (int step 0; step 30; step) { if (isPal(M)) { cout STEP step endl; return 0; } if (step 30) break; string rev M; reverse(rev.begin(), rev.end()); M add(M, rev); } cout Impossible! endl; return 0; }几个细节值得说明val和toChar负责字符和数字之间的转换覆盖16进制的A-F。如果输入里有小写字母最好在输入后统一转大写for (char c : M) c toupper(c);。add函数中while循环条件带carry所以最高位的进位不会丢。主循环用step从0到30先判断再决定是否继续加。这样初始就是回文数时会输出STEP0第30次加法后才变成回文的也能输出STEP30不会漏判。3.2 Python参考实现Python写起来更短适合快速验证思路def to_val(ch): if 0 ch 9: return ord(ch) - ord(0) return ord(ch.upper()) - ord(A) 10 def to_char(x): return str(x) if x 10 else chr(ord(A) x - 10) def add(a, b, base): res [] carry 0 i, j len(a) - 1, len(b) - 1 while i 0 or j 0 or carry: s carry if i 0: s to_val(a[i]) i - 1 if j 0: s to_val(b[j]) j - 1 res.append(to_char(s % base)) carry s // base return .join(reversed(res)) n int(input()) m input().strip().upper() for step in range(31): if m m[::-1]: print(fSTEP{step}) break if step 30: print(Impossible!) break m add(m, m[::-1], n)Python的m[::-1]不会改变原字符串所以C里“拷贝后再反转”的问题在Python里不存在。但要注意.join(reversed(res))的顺序res是从低位开始存储的必须反转回来才是正确结果。3.3 时间复杂度与数据范围单次加法扫描整个字符串回文判断也扫描一次所以每轮是O(L)L是当前数字长度。因为每加一次最多增加1位所以从初始长度L0开始30轮后长度不超过L030。总复杂度O(30 * (L0 30))。就算初始M有100位字符操作也就几千次在评测系统上几乎是0ms。这道题真正的难点从来不是性能而是逻辑细节。4. 变式题与常见误区进制、回文、高精度三者的组合4.1 误区一先把M转成十进制再算有些同学会问能不能先把M转成十进制在十进制里做高精度加法再转回N进制理论上是可行的但不推荐。原因在于M本身是N进制数按N进制加法规则直接在字符串上模拟不需要经过十进制。如果先转十进制100位的N进制数转成十进制后依旧是个大数还得再写一套十进制高精度做完再转回去代码量直接翻倍。正确的思路是把“N进制高精度加法”封装成一个函数任何进制都通用。只要处理好toChar和val代码可以兼容2到16进制这也是这道题最值得收藏的模板价值。4.2 误区二判断回文和生成倒序数混在一起判断回文的本质是“原串 反转串”。生成倒序数的本质是“取反转串”。这两个操作看起来很像但使用场景完全不同。每次循环里正确的顺序是先判断当前串是否是回文如果不是生成反转串做加法把结果作为新的当前串。如果在判断回文时把原串反转了下一步生成反转串得到的其实是一开始的顺序结果必然会错。C的isPal函数内部要拷贝一份再reverseadd函数里也要先拷贝原串再反转。4.3 误区三输入字母大小写不一致NOIP1999原题给的是大写A-F但有些数据或变式题可能给小写。稳妥起见读入之后统一转大写Cfor (char c : M) c toupper(c);Pythonm input().strip().upper()否则val函数遇到小写字母会返回错误的结果。写这种进制字符串题目先搞定字符和数字互转再写主逻辑能省下大量调试时间。4.4 从这道题延伸出去的变式如果题目改成“输出每一轮的结果”你只需在循环里把M打印出来。如果改成“步数上限是1000”调整range和判断逻辑就行算法完全不用变。如果以后遇到“高精度回文数”“N进制加法”类题目核心模板就是这套val、toChar、add、isPal四个函数组合使用。我在训练时经常把这套模板拆给学生先让他们单独测加法函数再测回文判断最后组合。任何一个函数都能独立验证组合起来出错时也好定位。5. 我重做这道题时踩过的坑以及自查清单5.1 最隐蔽的坑循环少判了一步我第一次写的时候用的是while (step 30)循环里先加再判断while (step 30) { M add(M, rev(M)); step; if (isPal(M)) { ... } }这样有两个问题一是初始M本身是回文数时会先加一次再判断导致答案从STEP0变成STEP1二是某个数据如果恰好需要30步加法最后一次加法在step29到step30之间完成加法完成后循环条件step 30已经为假根本不会执行isPal判断结果输出Impossible!但正确答案是STEP30。改成for (int step 0; step 30; step)每次先判断再决定是否继续加问题就消失了。5.2 最高位进位的坑写add函数时如果while条件忘加|| carry遇到类似999999的数据结果会变成998而不是1998。虽然在回文数题目里不一定出现这种极端数据但评测数据完全可能覆盖。处理办法是while循环条件里包含carry或者在循环结束后单独判断carry是否为1。我推荐前者更通用以后做其他高精度题也安全。5.3 16进制字母转换的坑最初写val函数时只处理了0到9结果遇到N16、MA时返回一个奇怪的数甚至负数。后来老老实实补上字母分支。给新手一个建议进制字符串相关的题目先把字符转换函数写好并单独测试再写主逻辑。它们一旦出错样例可能都过不了。5.4 前导零的问题有人会担心相加后结果最高位如果是0会不会生成“0123”这种字符串实际上在本题的合法数据里不会出现因为M的首位不为0倒序数的首位是M的末位两个最高位相加至少为1最高位不可能是0。但如果以后做更通用的高精度函数可以在最后加一步去前导零保证健壮性。5.5 我现在的自查清单每次提交前我都会对照这份清单检查一遍初始M是不是回文如果是必须输出STEP0。第30步加法完成后有没有再做一次回文判断最高位如果有进位有没有写进结果串A-F的字符转换是否覆盖了大小写有没有把“判断回文”和“取反转串”搞混导致原串被意外反转输出格式是不是STEP数字等号旁边有没有多余空格Impossible!后面的感叹号有没有漏掉这些细节在题目要求里写得清清楚楚但恰恰是丢分最多的地方。5.6 一点个人体会我平时带训练时经常让学员先不看代码用自己的话把“N进制高精度加法”的竖式过程写一遍再动手写代码。回文数这道题真正考察的不是“你会不会判断回文数”而是你能不能把竖式加法、进制转换、回文判断三件事干净地组合在一起并且在30步边界条件下不犯低级错误。最后分享一个调试技巧在循环里临时打印M和step用样例数据跑一遍观察数字长度变化是否合理。如果某一步字符串长度突然减少或者出现了超出当前进制的字符比如N10时出现字母那多半是字符转换写错了。排查完把打印语句删掉再提交就很稳。这道题虽然年头久但作为高精度入门的“试金石”值得反复做几遍。