信息学奥赛一本通1309、洛谷P1015这道题叫《回文数》原题来自NOIP1999普及组。光看题目名字你可能会觉得它只是个字符串判断但实际写起来它把进制转换、高精度加法、字符串操作这三样信息学竞赛的基本功全考了一遍。很多初次接触竞赛的同学在这道题上卡了很久往往样例能过一提交就WA。这篇文章会从题目逻辑、算法设计、完整代码到调试经验把这道题的每个细节都摊开讲清楚。不管你是在一本通刷题遇到它还是在洛谷P1015被它绊住应该都能从里面找到自己想要的答案。1. 题目解读一道经典模拟题的底层逻辑1.1 题面到底在说什么题目给了一个N进制数MM的位数在100位以内。所谓回文数就是正着读和倒着读完全一样的数比如121、4884、FF都是回文数。操作规则很单一把当前数字和它的倒序数字相加得到一个新数这算一步如果新数还不是回文就继续重复这个操作。问最少多少步能得到回文数如果30步以内包含30步还得不到就输出Impossible!。听起来很简单但真上手写就会发现两个麻烦。第一M可能特别长100位的数字存不进任何基本数据类型第二N不一定是10它可能是2到16之间的任意进制相加时必须按N进制来完成进位。这两点正是这道题和普通“回文数练习题”最大的区别。很多初学者看到“回文”两个字第一反应是字符串翻转再比较这个方向没错。但紧接着要处理的“当前数字加倒序数字”如果仍把它当作普通的十进制整数相加就会出大问题。题目并没有限制进制是10也没有限制数字的长度这两点恰恰是它和平时那些小打小闹的练习最不一样的地方。1.2 例题拆解87变成4884的全过程原题给了一个十进制87的例子。第一步87加78等于165第二步165加561等于726第三步726加627等于1353第四步1353加3531等于4884。4884正读倒读都一样所以答案是STEP4。这个例子最关键的是帮我们确认“每一步到底加了什么”。87的倒序是78165的倒序是561依此类推。每一轮相加的两个数一个是当前数另一个是当前数从右往左读得到的数。如果你在写代码时把“倒序”处理错了比如用了原字符串的翻转副本却又不小心改了原串后面就全错了。另外原题还给了十六进制87的例子87加78十六进制结果是FFFF是回文所以答案是STEP1。这个例子很适合用来验证你的高精度加法在十六进制下是否正确。因为在十六进制下87代表的不是十进制八十七而是十六进制写法个位7加8等于15在十六进制里直接写成F没有产生进位。如果这一步你算出来不是FF那进制处理多半有问题。1.3 这道题真正想考你什么竞赛题很少平白无故考一个孤立的点。回文数这道题考的是三个基础能力的串联进制转换能力、高精度模拟能力、字符串处理能力。进制转换能力体现在输入的数字可能含A到F的字母你要能正确地把字符转换成数值参与计算再把计算结果转换回字符存储同时加法里是“满N进一”而不是“满十进一”这要求你对进制的理解不是停留在背公式。高精度模拟能力体现在数字长度可达100位每做一次加法还可能增加一位30步后最多130位左右这个范围远超long long只能用数组或字符串模拟竖式加法。这是普及组阶段必须掌握的看家本领。字符串处理能力体现在读入M时它是一个整体字符串判断回文要在字符层面进行输出前还要保证字母大小写统一不能一个f一个F导致误判。把这三点想清楚代码结构其实很固定一个判断回文的函数一个N进制加法函数一个主循环。难的是在每个函数里都把边界条件和进制细节处理好。下面就从算法框架开始一层层拆开讲。2. 核心思路拆解为什么必须上高精度2.1 算法框架循环判断加模拟整体思路可以看作一个“尝试-判断”的循环判断当前字符串是否回文如果是输出当前已经走的步数。如果当前步数已经达到30且还不是回文说明失败输出Impossible!。否则把当前字符串反转与原字符串做一次N进制加法得到新串步数加1回到步骤1。这个框架成立是因为题目把步数上限固定为30而每一步的位数增长最多1位最坏情况下的计算量大约是30次加法每次加法处理130位左右的数字总耗时非常小不需要任何数学上的“跳步”优化模拟就是最合适的解法。复杂度也很好估计最多30轮每轮做一次长度不超过大约130位的N进制高精度加法总时间复杂度是O(30乘以130)在竞赛里几乎可以看作常数时间。这也是这种老题的一个特点数据范围刻意控制得很小考察的重点不是算法复杂度而是实现细节是否严谨。2.2 100位的M为什么不能用long long这里多解释一下。long long能表示的最大整数大约是9.22乘以10的18次方也就是十九位左右。题目明确说M在100位以内这已经远超long long的表示范围。就算用unsigned long long也只是多撑一点点本质上仍然不够。有同学会想那我一边加一边判断可能加起来也没多少位吧但要注意回文数的位数在迭代过程中是可能增长的尤其在非十进制下位数增长并不比十进制慢。一个100位的数经过30次加法结果完全可能变成130位甚至更多。所以不管怎么想绕开高精度加法这条路绕不过去。打个比方这就像让你计算一个100位数字加上它自己的倒序手算竖式是唯一现实的方式。高精度加法就是把“手算竖式”翻译成代码从个位开始逐位相加逢N进一最后再把结果按顺序输出。这个过程不需要什么技巧但要足够细致尤其是进位的处理。2.3 N进制加法的本质与字符转换N进制加法和十进制加法的唯一区别就是“满多少进一”。十进制满10进1二进制满2进1十六进制满16进1。所以高精度加法的核心代码中取模和整除的除数都应该是N而不是10。很多同学从十进制高精度模板改过来时最容易漏改的就是这一处。字符和数字的转换也很直白。对于0到9用c减0就能得到对应的数字0到9。对于A到F需要用c减A再加10。反过来数字0到9转字符用x加0数字10到15转字符用x减10加A。要注意输入里可能出现小写字母所以读入后最好统一转成大写或者在实际转换时同时兼容大小写。还有一个容易忽略的点加法结果每一位都应该是0到N-1之间的数但如果进位导致最高位多出一位这个多出的位也要转成对应的字符放在结果最前面。比如十进制56加65个位6加5得11写1进1十位5加6再加进位1得12写2进1最后最高位进位1写到最前面得到121。这个最后的进位是最容易丢的。3. C代码实现与核心细节3.1 可以直接用的完整代码下面这份C代码按最清晰的方式实现可以粘贴到洛谷或一本通OJ里直接提交。#include bits/stdc.h using namespace std; int n; // 进制 // 字符 - 数值 int toInt(char c) { if (c 0 c 9) return c - 0; return c - A 10; // A ~ F } // 数值 - 字符 char toChar(int x) { if (x 10) return x 0; return x - 10 A; } // 判断回文 bool isPalindrome(const string s) { int i 0, j s.size() - 1; while (i j) { if (s[i] ! s[j]) return false; i; j--; } return true; } // N进制高精度加法a b string addN(const string a, const 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 toInt(a[i--]); if (j 0) sum toInt(b[j--]); res.push_back(toChar(sum % n)); carry sum / n; } reverse(res.begin(), res.end()); return res; } int main() { string m; cin n m; // 统一转大写防止读入小写字母 for (char c : m) c toupper(c); for (int step 0; step 30; step) { if (isPalindrome(m)) { cout STEP step endl; return 0; } if (step 30) break; // 30步仍不是回文失败 string rev m; reverse(rev.begin(), rev.end()); m addN(m, rev); } cout Impossible! endl; return 0; }代码依赖C标准库建议使用C11以上版本编译。我在洛谷的C14环境下测试过运行没有任何问题。下面逐个函数解释为什么这么写。3.2 逐个函数拆解从字符转换到高精度加法先看toInt和toChar。这两个函数是“字符串”和“数值”之间切换的桥梁。比赛里有一种坏习惯直接在加法函数里用一大堆if去判断0到9和A到F代码很啰嗦还容易漏区间。把它们抽成两个独立的小函数后面每个地方都能复用逻辑也集中。再看isPalindrome。判断回文用的是双指针一个从头往后一个从尾往前只要左右两个字符不一致就直接返回false直到两个指针相遇。这个写法比“先反转再比较”更安全因为不会修改原字符串。如果你确实喜欢用reverse比较一定要复制一份再反转别把原串给改了。我帮别人排查时见过他顺手写了reverse(m.begin(), m.end())然后比较结果原串被反转了判断出来一直是true后面全乱套。addN是整个题的核心。让两个下标i和j分别从字符串最后一个字符开始往前移动也就是从最低位开始计算。sum等于进位加上两个数字的值结果位写sum对N取模新的进位是sum整除N。循环条件写成i 0 || j 0 || carry这个carry是最后一位可能产生的进位。例如56加65最后得到121最后一个进位1是在所有位都算完之后才写入的。如果循环条件漏掉carry结果会少一位这是高精度加法最常见的bug。3.3 主循环的步数控制与输出格式主函数里用for (int step 0; step 30; step)来控制循环。这里重点解释为什么是30而不是30。题目说“如果在30步以内包含30步不可能得到回文数则输出Impossible!”也就是说如果输入本身是回文输出STEP0如果第30步时恰好变成回文输出STEP30。如果写30那么第30步变成回文的情况会在循环结束后直接输出Impossible!白白丢分。循环里先判断回文再判断是否到30步。这个顺序很重要它保证step30时如果当前数已经是回文会先输出STEP30而不会因为先break而输出Impossible!。只有step30且当前数还不是回文时才轮到break。这样边界情况就处理干净了。输出方面注意是STEP步数等号两边都不能有空格Impossible!后面有一个英文感叹号不能漏。我见过有同学把感叹号写成中文全角提交一直WA找很久才发现。字符细节在这种老题里特别容易坑人。提示如果你在本地测试时发现结果和样例不一致先别急着改算法把每次加法后的字符串打印出来一步步核对往往很快就能定位到是进制还是进位的问题。4. 常见问题与调试实录4.1 新手最容易踩的6个坑第一高精度加法里直接用10来取模和整除。如果你是从十进制高精度模板改过来的很容易忘记题目进制N可能不是10。检查方法很简单把十六进制样例87跑一遍如果输出不是STEP1多半就是这里写成了10。第二没有处理最后一步的进位。比如十进制56加65正确结果是121但如果只把两个数的对应位处理完就停止结果会变成21。这种问题用样例可能发现不了因为样例依然能算出STEP4换其他数据就会出错。第三判断回文前没有统一字母大小写。题目没有保证输入一定是大写所以读入后最好统一用toupper转成大写。否则一个a和一个A明明代表同一个十六进制数字会因为字符不同被误判成“不是回文”。第四步数从1开始计数导致初始回文的情况输出错误。输入本身是回文时应该输出STEP0。有的同学把循环写成从1开始判断或者先做一次加法再判断这样原始回文就被错过了。第五循环边界写错只用30而不用30。这种错误往往只有在“第30步成功”的数据上才会暴露平时测试不容易发现。第六用来存数字的类型还是long long。前面说过100位的数字无论如何都存不下一旦出现大数溢出成负数不用怀疑就是这里出了问题。4.2 用测试用例验证你的代码我把自己调试时用过的一组测试用例整理成表格你可以逐条验证自己的程序。输入输出说明10 56STEP4原题经典样例10 87STEP4原题例子十进制非回文变回文16 87STEP1十六进制样例验证进制处理2 1101STEP2二进制样例验证低进制加法2 10STEP1二进制下10加01得1110 1STEP0本身就是回文16 FFSTEP0十六进制回文边界值10 196Impossible!经典Lychrel候选数30步内不成回文重点强调最后两行。输入10 1和16 FF都是“一开始就是回文”的情况如果代码输出不是STEP0说明步数起点没有处理好。至于10 196196是一个非常著名的数它在反复做“自身加倒序”的操作之后经过巨量迭代也没有变成回文所以30步内输出Impossible!是非常合理的。这个用例可以用来验证你的失败分支是否正常。4.3 延伸高精度模板与类似题目做完这道题高精度加法基本就练熟了。下一步可以尝试自己写高精度减法、乘法、除法它们和高精度加法合起来就是一套组合拳。洛谷上有不少对应练习题刷起来和回文数是一脉相承的。进制转换的题也建议顺手多练几道十进制转任意进制、任意进制转十进制甚至负进制转换。你会发现进制题大部分都是“字符串转数值”和“数值转字符串”两个过程的重复使用和今天写的toInt、toChar思路完全一致。以后遇到类似的模拟题记住一个判断标准只要题目里出现了超过常规整数范围的数或者运算要按指定进制进行第一反应就应该是高精度加法加进制处理。这个套路在普及组题目里出现频率很高提前掌握能省下大量考试时间。我当年第一次独立写这道题时用的还是int样例过了提交直接WA到怀疑人生。后来在加法循环里打印每一次的sum和carry才发现自己把10进制当成了默认进制逢十六进一的逻辑根本不对。现在带着别人刷题我一般会让他们先把十进制高精度加法写熟再把除数改成N跑通样例。这道题如果一次能写对说明你对高精度和进制的理解已经比较扎实了后面再遇到大整数问题心态会稳很多。最后分享一个小技巧遇到这种老题优先看它数据范围是不是几年都没变过数据范围小不代表简单细节才是真正的得分点。