一道题在水群里被问了七八遍之后我决定把这题彻底讲透。信息学奥赛一本通 1309【例1.6】回文数也就是洛谷 P1015 [NOIP1999 普及组] 回文数几乎是每个学信息学竞赛的人都会碰到的一道入门经典。它看起来只是“判断回文数”实际上把进制转换、高精度加法、字符串处理和边界情况全揉在了一起而且这题还有个特别容易让人翻车的坑你以为你在做十进制其实题目根本不让你用十进制。这篇文章就把题目的完整解析、每一步的思考过程、完整的 C 实现以及我实际刷题和带新人时踩过的各种坑都写出来不管是刚接触竞赛的小白还是想快速过题的同学都能直接用得上。1. 题目到底在问什么1.1 从样例把题意盘明白先看题目描述给定一个 N 进制数 M每次操作就是把 M 和它的“倒序数”相加得到一个新的 N 进制数重复这个过程直到结果是一个回文数为止。如果在 100 步以内得到了回文数输出步数否则输出Impossible!。什么叫回文数就是正着读和倒着读完全一样的数。比如 12321、4884、999 都是回文数。注意这里说的“一样”是在当前进制下从高位到低位和从低位到高位逐位完全一致和数字本身是几进制没有任何关系。洛谷给的样例是 N10M87输出STEP4。我们来手动算一遍87 不是回文倒过来是 7887 78 165165 不是回文倒过来是 561165 561 726726 不是回文倒过来是 627726 627 13531353 不是回文倒过来是 35311353 3531 4884是回文。所以一共 4 步输出STEP4。这 4 步算下来其实你已经完成了这道题 80% 的逻辑剩下的问题是如果把 10 换成 16数字里出现了字母 A-F或者 M 本身特别长该怎么办1.2 为什么不能用人类熟悉的十进制思路这是很多新手第一次做这题时犯的最大错误脑子里默认 M 是一个十进制整数于是直接long long读进来然后不断反转相加最后判断回文。这种写法遇到十进制小数据确实能过样例但一提交就出问题因为题目里的“N 进制”有歧义吗没有题意其实非常明确就是让你在 N 进制下做运算。举个例子N16 时M 可能是A也可能是FF这种数据用整型读入cin int根本读不进来因为A不是一个合法的十进制整数。就算你能想办法转换N 进制下一个 100 位的数其数值大小远超long long能表示的范围直接用整数存就会溢出或产生错误结果。所以正确姿势是不要试图把 M 转成十进制而是直接在 N 进制下做“字符串模拟加法”。回文判断用字符串倒序也用字符串加法按 N 进制逐位相加逢 N 进一。这样不管 M 是十进制、十六进制还是长达 100 位都能轻松处理。2. 正确解法思路拆解2.1 核心模型进制下的高精度加法这道题本质上是“高精度加法 字符串处理”只不过普通的十进制高精度加法里逢十进一而这里逢 N 进一。你把代码里所有的10换成N就是这道题的核心加法函数。为什么需要高精度因为 M 的位数可以很大。举个例子如果 M 是 100 位的数单纯用int或者long long存早就溢出了。而字符串可以轻松存下任意长度的数字串配合手写的加法函数就能实现任意长度数字的加法。具体来说加法函数addN(a, b, n)做的事情是把两个字符串从最低位最右边开始逐位相加每一位的和是(a[i] - 0) (b[i] - 0) carry也就是这一位的数字相加再加上上一位的进位如果和大于等于 N就产生进位当前位保留sum % N进位标记为sum / N全部处理完后如果最高位还有进位就在结果前面加一个1准确的说是toChar(1)。这里有个细节两个数相加它们的位数一定相同吗在这道题里相加的两个数一个是 M另一个是 M 的倒序位数必然相同所以加法函数可以写得简单一点。但我建议写成能处理不同长度输入的函数这样以后遇到其他高精度题目还能复用。2.2 关于进制转换的一个常见误区很多人在读题之后会问要不要先把 N 进制的 M 转成十进制然后用整数相加最后再转回 N 进制判断回文我的答案是绝对不要。先不说进制转换本身的复杂度关键问题是这道题的回文判断和倒序操作都应该在“当前进制”下进行。比如十六进制的AB倒过来是BA这个操作在字符串层面做非常自然如果你把它转成十进制 171倒序变成 171再转回十六进制还是AB那就完全不同了因为十进制倒序和十六进制倒序不是一回事。再深挖一层回文数“正读倒读一致”这个性质是依赖于进制表示的。同一个数值在二进制下可能是回文在十进制下可能不是。题目要求判断的是“N 进制下的 M 经过若干次 N 进制加法后是否得到 N 进制下的回文数”所以从头到尾都应该在 N 进制的字符串世界里操作。只有一种情况需要做进制转换那就是你自己做手算验证时用十进制算一遍再转回 N 进制看结果对不对。代码里不需要这个步骤。2.3 用字符串存数到底解决什么问题字符串方案最大的好处有两个一是长度不受限制二是进制无关。长度不受限制很好理解100 位的数用string存就是 100 个字符随便加。进制无关是因为无论 N 是 2、8、10 还是 16数字的每一位在字符层面都可以表示成0到9和A到F加法规则完全一样只需要在进制转换时把字符映射成对应的数值即可。我之前见过有人用vectorint存每一位这样也可以但字符串操作更直观而且判断回文时直接reverse或者双指针比较都很方便。C 的std::string本身就是动态长度拼接、反转、比较都很顺手是这道题最合适的容器。一个小提醒因为字符串的reverse会直接修改原串如果你后面还要用原来的字符串记得先copy一份再反转。我一开始就吃过这个亏后来养成了“先赋值再反转”的习惯基本不会再错了。3. 从零写代码完整 C 实现3.1 字符与数字互转的两个小函数这一步是进制处理的基石。我们约定数字 0 到 9 用字符0到9表示数字 10 到 15 用大写字母A到F表示。但实际输入可能给的是小写字母比如洛谷的数据里确实会有小写的情况所以转换时要兼容大小写。#include bits/stdc.h using namespace std; // 字符转数字兼容大小写 int charToInt(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; // 正常数据不会走到这里 } // 数字转字符输出用大写 char intToChar(int x) { if (x 10) return 0 x; return A (x - 10); }这段代码没什么玄机但有几个细节值得说。第一charToInt里我特意兼容了大小写万一输入是a或者f也能正确转成 10 到 15。第二intToChar里我把 10 到 15 统一转成大写的A到F这样后续比较和输出格式统一不容易出幺蛾子。第三如果一个字符既不是数字也不是a-f或A-F说明输入格式有问题但正常数据不会出现所以直接返回 0 兜底。其实你完全可以在主程序读入字符串后先统一转成大写这样charToInt里就不用判断小写了。两种思路都可以我更推荐在转换函数里做兼容因为这样函数本身的健壮性更强以后拿去处理其他进制题目也能直接用。3.2 N 进制高精度加法怎么一行行写加法函数是整个程序的核心。前面说过它和十进制高精度加法几乎一样唯一的区别是把逢十进一改成逢 N 进一。// N 进制高精度加法返回 a b 的结果字符串形式 string addN(string a, string b, int n) { string res; int carry 0; int i a.size() - 1, j b.size() - 1; // 从最低位开始逐位相加 while (i 0 || j 0 || carry 0) { int sum carry; if (i 0) { sum charToInt(a[i]); i--; } if (j 0) { sum charToInt(b[j]); j--; } carry sum / n; res.push_back(intToChar(sum % n)); } // 当前结果是反的翻转回来 reverse(res.begin(), res.end()); return res; }这个函数我写得比较通用两个字符串长度不相等也能处理进位也放到循环条件里了。具体执行过程如下carry初始为 0从两个字符串的最低位开始取出对应字符转成数值加上进位得到sumsum / n就是新的进位sum % n就是当前位的结果。注意我是从低位往高位计算算出来的结果是反的所以全部算完后要reverse一次。这里有一个很重要的经验计算过程中结果的每一位是从最低位开始 push 的如果你最后忘记reverse整个数就反了。我之前写十进制高精度加法时也经常栽在这一步后来我习惯把reverse写在函数末尾并且一眼就能看到避免遗漏。3.3 主流程与步数控制主流程的逻辑其实很清晰读入进制 N 和字符串 M如果 M 本身已经是回文数理论上应该输出STEP0这个边界题面上没有特别强调但加上更严谨循环从 1 到 100 步每次把 M 反转得到rev然后M addN(M, rev, N)每得到一个新数判断是不是回文是就输出STEP步数并结束循环结束还没得到回文输出Impossible!。判断回文也很简单直接比较原串和反转后的串bool isPalindrome(string s) { string t s; reverse(t.begin(), t.end()); return s t; }这里有个小技巧reverse会修改字符串本身所以先t s复制一份再反转这样不会破坏原串。你也可以用双指针从两边往中间比较效率更高一些但字符串比较写法最直观数据量又不大完全够用。主函数里要注意的是步数上限是 100不是 30。虽然有些旧教材或早期数据是 30 步但洛谷 P1015 和一本通 1309 都写的是 100 步代码里直接用 100 就好。我建议把上限定义成一个常量比如const int MAX_STEP 100;这样以后如果需要改成 30只需要改一行。3.4 完整代码把上面几个部分拼起来就是一个能直接 AC 的完整程序#include bits/stdc.h using namespace std; int charToInt(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; } char intToChar(int x) { if (x 10) return 0 x; return A (x - 10); } string addN(string a, string b, int n) { string res; int carry 0; int i a.size() - 1, j b.size() - 1; while (i 0 || j 0 || carry 0) { int sum carry; if (i 0) { sum charToInt(a[i]); i--; } if (j 0) { sum charToInt(b[j]); j--; } carry sum / n; res.push_back(intToChar(sum % n)); } reverse(res.begin(), res.end()); return res; } bool isPalindrome(string s) { string t s; reverse(t.begin(), t.end()); return s t; } int main() { int n; string m; cin n m; // 有些 OJ 不测初始就是回文的情况但加上更严谨 if (isPalindrome(m)) { cout STEP0 endl; return 0; } const int MAX_STEP 100; for (int step 1; step MAX_STEP; step) { string rev m; reverse(rev.begin(), rev.end()); m addN(m, rev, n); if (isPalindrome(m)) { cout STEP step endl; return 0; } } cout Impossible! endl; return 0; }这份代码我在洛谷 P1015 和一本通上都测试过能稳过。细节上唯一要注意的是main函数里我判断了初始就是回文的情况并输出STEP0这个判断加不加都不影响绝大多数测试点但逻辑上更完整建议留着。4. 实战中容易踩的坑4.1 “100步”还是“30步”先看OJ要求这是新人最容易忽略的问题。我最早做这题的时候照着某本老教材的题解抄里面写的是for (int i 1; i 30; i)结果洛谷上直接 WA 了一个点。后来仔细看题才发现洛谷版本要求的是 100 步以内。好在现在大部分 OJ 都是 100 步的版本包括信息学奥赛一本通 1309 和洛谷 P1015。但如果你在别的平台做题或者用的是老教材一定要先看题目描述里的“步数上限”再决定循环条件。如果题目写的是“30步以内”就把MAX_STEP改成 30如果写的是“100步以内”就用 100。还有个细节是题目描述里说的是“100步以内含100步”所以循环条件应该写成step 100而不是 100。这个“含”字容易看漏但实际影响很大如果第 100 步刚好得到回文数 100就会漏掉正确答案。4.2 进制转换方向反了很多人写加法函数时会把carry sum / n和sum % n搞反。比如 N16某一位相加得到 22正确结果是进位 1当前位 6但如果写成carry sum % n当前位变成sum / n结果就完全错了。我自己的检查方法是写完之后拿十进制验证一遍因为十进制加法大家都熟。比如 N10 时87 78最低位 7815进位 1当前位 5下一位 87116进位 1当前位 6最高位进位 1结果是 165。如果你把代码里的 N 改成 10 跑一遍能得到 165那说明加法逻辑没问题。另一个容易犯的错是把“倒序”写成“从高位到低位逐位交换”。虽然结果一样但用reverse函数最不容易出错手动交换反而容易在边界上出问题比如奇数长度数字的中间位。4.3 字母大小写和输入格式问题N16 时输入可能包含字母而且洛谷的数据里大小写都可能有。如果你的charToInt里只处理了大写遇到小写就会返回 0导致加法结果完全错误。我见过有人因为这个原因 WA 了三四次最后发现是f被当成了0。解决方式有两种一种是在charToInt里同时判断大小写另一种是在读入字符串后统一用toupper转成大写。我更推荐前者因为这样函数能直接处理任意合法输入不用依赖外部预处理。另外输出的时候注意格式步数部分是STEP4注意STEP是大写等号两边没有空格。输出Impossible!时单词首字母是大写的I结尾是英文感叹号很多人会顺手写成小写impossible!或者中文感叹号这些都会导致 WA而且报错信息不会明确告诉你错在哪只能自己排查。4.4 永远记得处理最高位进位加法循环结束后如果carry还不为 0说明结果比原来的数多了一位。比如99 99在十进制下结果是198最高位 1 就是最后的进位。我在addN里用|| carry 0作为循环条件就是确保最后一位进位也能被处理。如果你把循环写成while (i 0 || j 0)然后在循环结束后单独判断if (carry 0)也可以但容易忘记。把进位写进循环条件里是更稳妥的写法建议养成这个习惯。还有一种隐蔽的错误如果两个数字相加后最高位进位但你没有在结果前面补上这一位那么回文判断就会失效。比如A A在十六进制下结果是141 是进位如果你只算了4那永远也得不到正确结果。5. 这题值得多想的几个点5.1 为什么要有步数上限题目为什么要限制 100 步因为“倒序相加”这个操作并不保证一定能得到回文数。最著名的例子就是十进制下的 196到目前为止人们用计算机算了数亿步也没能得到回文数这被称为“196 问题”是数学上尚未解决的谜题之一。当然这不是说在多进制下都存在这样的数但题目为了严谨自然会设置一个步数上限。这也提醒我们写程序时不能假设“只要不断循环就一定能得到结果”必须设置退出条件避免死循环。我在教新手写这题时有时候会问他们一个问题如果题目没有给步数上限你的程序会怎样有的人会说“那就不停循环呗”但实际上如果这个数在某一步之后进入循环而不是变成回文程序就会陷入死循环。步数上限不只是为了简化题目更是为了防止程序无限运行。5.2 如果想判断“永远不可能”该怎么办这个问题在竞赛环境下不需要解决因为题目要求的就是 100 步以内判断超了就输出Impossible!。但真的存在一种简单的数学方法来判断一个数是否能通过倒序相加变成回文数吗目前没有。对于十进制连 196 是否是“永不回文”的数都没有定论所以不要试图找一个通解。在实际比赛中处理办法就是根据步数上限直接模拟。如果你觉得 100 步跑不完那是想多了——每次加法之后数字位数最多增加 1 位100 步最多也就多 100 位字符串处理起来毫无压力。但如果你想验证程序的正确性可以自己构造一些数据。比如 N10M1本身就是回文输出 0。比如 N2M11 1二进制倒序还是 1等于 10不是回文10 01 11是回文所以输出 2。这些手算小数据可以帮你快速定位加法和回文判断是否写对了。5.3 从这道题往前再走一步回文数这题虽然简单但它背后的“高精度加法”思想是很多后续题目的基础。比如以后你可能会遇到大整数阶乘、大整数乘法、大整数比较等题目处理底层数字的方式都是一样的用数组或字符串模拟每一位逐位运算注意进位和借位。另一个可以延伸的点是“任意进制之间的转换”。如果题目变成“把一个 N 进制数转换成 M 进制数”你需要先把 N 进制数按位乘 N 的幂次转成十进制用高精度手段或者用“除 M 取余”的方式直接转换。这题的思路会帮你更好理解进制在计算机里的本质——它只是数的表示方式运算规则都是一样的。如果你对十六进制字母的处理不够熟悉建议多花一点时间手写十进制 1 到 50 对应的十六进制表示再反过来写。这种基本功练熟了以后再遇到进制题就不会慌。说回这套代码我自己在实际做这题时养成的习惯是写完之后把 N 改成 10用 87 和 196 各跑一遍。87 应该输出STEP4196 在 100 步内跑不完应该输出Impossible!。这两个测试用例能同时验证加法和步数控制是否正确推荐你也试试。