企业官网建设流程全解析

信息学奥赛一本通1309、洛谷P1015，这道题叫《回文数》，原题来自NOIP1999普及组。光看题目名字，你可能会觉得它只是个字符串判断，但实际写起来，它把进制转换、高精度加法、字符串操作这三样信息学竞赛的基本功全考了一遍。很多初次接触竞赛的同学在这道题上卡了很久，往往样例能过，一提交就WA。这篇文章会从题目逻辑、算法设计、完整代码到调试经验，把这道题的每个细节都摊开讲清楚。不管你是在一本通刷题遇到它，还是在洛谷P1015被它绊住，应该都能从里面找到自己想要的答案。

1. 题目解读：一道经典模拟题的底层逻辑

1.1 题面到底在说什么

题目给了一个N进制数M，M的位数在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正读倒读都一样，所以答案是STEP=4。

这个例子最关键的是帮我们确认“每一步到底加了什么”。87的倒序是78，165的倒序是561，依此类推。每一轮相加的两个数，一个是当前数，另一个是当前数从右往左读得到的数。如果你在写代码时把“倒序”处理错了，比如用了原字符串的翻转副本却又不小心改了原串，后面就全错了。

另外，原题还给了十六进制87的例子：87加78，十六进制结果是FF，FF是回文，所以答案是STEP=1。这个例子很适合用来验证你的高精度加法在十六进制下是否正确。因为在十六进制下，87代表的不是十进制八十七，而是十六进制写法，个位7加8等于15，在十六进制里直接写成F，没有产生进位。如果这一步你算出来不是FF，那进制处理多半有问题。

1.3 这道题真正想考你什么

竞赛题很少平白无故考一个孤立的点。回文数这道题，考的是三个基础能力的串联：进制转换能力、高精度模拟能力、字符串处理能力。

进制转换能力体现在：输入的数字可能含A到F的字母，你要能正确地把字符转换成数值参与计算，再把计算结果转换回字符存储；同时，加法里是“满N进一”而不是“满十进一”，这要求你对进制的理解不是停留在背公式。高精度模拟能力体现在：数字长度可达100位，每做一次加法还可能增加一位，30步后最多130位左右，这个范围远超long long，只能用数组或字符串模拟竖式加法。这是普及组阶段必须掌握的看家本领。字符串处理能力体现在：读入M时它是一个整体字符串，判断回文要在字符层面进行，输出前还要保证字母大小写统一，不能一个'f'一个'F'导致误判。

把这三点想清楚，代码结构其实很固定：一个判断回文的函数，一个N进制加法函数，一个主循环。难的是在每个函数里都把边界条件和进制细节处理好。下面就从算法框架开始，一层层拆开讲。

2. 核心思路拆解：为什么必须上高精度

2.1 算法框架：循环判断加模拟

整体思路可以看作一个“尝试-判断”的循环：

1. 判断当前字符串是否回文，如果是，输出当前已经走的步数。
2. 如果当前步数已经达到30且还不是回文，说明失败，输出Impossible!。
3. 否则，把当前字符串反转，与原字符串做一次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++标准库，建议使用C++11以上版本编译。我在洛谷的C++14环境下测试过，运行没有任何问题。下面逐个函数解释为什么这么写。

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!”，也就是说如果输入本身是回文，输出STEP=0；如果第30步时恰好变成回文，输出STEP=30。如果写<30，那么第30步变成回文的情况会在循环结束后直接输出Impossible!，白白丢分。

循环里先判断回文，再判断是否到30步。这个顺序很重要：它保证step=30时如果当前数已经是回文，会先输出STEP=30，而不会因为先break而输出Impossible!。只有step=30且当前数还不是回文时，才轮到break。这样边界情况就处理干净了。

输出方面，注意是STEP=步数，等号两边都不能有空格，Impossible!后面有一个英文感叹号，不能漏。我见过有同学把感叹号写成中文全角，提交一直WA，找很久才发现。字符细节在这种老题里特别容易坑人。

提示：如果你在本地测试时发现结果和样例不一致，先别急着改算法，把每次加法后的字符串打印出来，一步步核对，往往很快就能定位到是进制还是进位的问题。

4. 常见问题与调试实录

4.1 新手最容易踩的6个坑

第一，高精度加法里直接用10来取模和整除。如果你是从十进制高精度模板改过来的，很容易忘记题目进制N可能不是10。检查方法很简单：把十六进制样例87跑一遍，如果输出不是STEP=1，多半就是这里写成了10。

第二，没有处理最后一步的进位。比如十进制56加65，正确结果是121，但如果只把两个数的对应位处理完就停止，结果会变成21。这种问题用样例可能发现不了，因为样例依然能算出STEP=4，换其他数据就会出错。

第三，判断回文前没有统一字母大小写。题目没有保证输入一定是大写，所以读入后最好统一用toupper转成大写。否则一个'a'和一个'A'明明代表同一个十六进制数字，会因为字符不同被误判成“不是回文”。

第四，步数从1开始计数，导致初始回文的情况输出错误。输入本身是回文时应该输出STEP=0。有的同学把循环写成从1开始判断，或者先做一次加法再判断，这样原始回文就被错过了。

第五，循环边界写错，只用<30而不用<=30。这种错误往往只有在“第30步成功”的数据上才会暴露，平时测试不容易发现。第六，用来存数字的类型还是long long。前面说过，100位的数字无论如何都存不下，一旦出现大数溢出成负数，不用怀疑，就是这里出了问题。

4.2 用测试用例验证你的代码

我把自己调试时用过的一组测试用例整理成表格，你可以逐条验证自己的程序。

重点强调最后两行。输入10 1和16 FF都是“一开始就是回文”的情况，如果代码输出不是STEP=0，说明步数起点没有处理好。至于10 196，196是一个非常著名的数，它在反复做“自身加倒序”的操作之后，经过巨量迭代也没有变成回文，所以30步内输出Impossible!是非常合理的。这个用例可以用来验证你的失败分支是否正常。

4.3 延伸：高精度模板与类似题目

做完这道题，高精度加法基本就练熟了。下一步可以尝试自己写高精度减法、乘法、除法，它们和高精度加法合起来就是一套组合拳。洛谷上有不少对应练习题，刷起来和回文数是一脉相承的。

进制转换的题也建议顺手多练几道：十进制转任意进制、任意进制转十进制，甚至负进制转换。你会发现，进制题大部分都是“字符串转数值”和“数值转字符串”两个过程的重复使用，和今天写的toInt、toChar思路完全一致。

以后遇到类似的模拟题，记住一个判断标准：只要题目里出现了超过常规整数范围的数，或者运算要按指定进制进行，第一反应就应该是高精度加法加进制处理。这个套路在普及组题目里出现频率很高，提前掌握能省下大量考试时间。

我当年第一次独立写这道题时，用的还是int，样例过了，提交直接WA到怀疑人生。后来在加法循环里打印每一次的sum和carry，才发现自己把10进制当成了默认进制，逢十六进一的逻辑根本不对。现在带着别人刷题，我一般会让他们先把十进制高精度加法写熟，再把除数改成N，跑通样例。这道题如果一次能写对，说明你对高精度和进制的理解已经比较扎实了，后面再遇到大整数问题，心态会稳很多。最后分享一个小技巧：遇到这种老题，优先看它数据范围是不是几年都没变过，数据范围小不代表简单，细节才是真正的得分点。