P1013 进制加法表：一行进位次数等于字符数值的巧妙规律

P1013NOIP 1998提高组的原题一道看着像字符串模拟、实际考数学观察的老题。题意一句话给你一张进制加法表让你反推出这是几进制、每个字符代表几。很多第一次见的人会被那张n×n的表格吓到以为要写大模拟其实只要抓住“进位”这个概念整道题就是一层窗户纸。这篇文章不打算只贴代码我想把从读题到AC的完整思考过程、推导规律、实现细节、踩坑记录都写出来适合正在备战提高组、或者刷字符串模拟题时卡住的人参考。1. 先搞懂题目到底在说什么1.1 原题描述和样例的基本格式洛谷P1013的输入是这样的第一行一个整数n接下来是一个n行n列的方阵。第一行第一列固定是“”号第一行的剩下n-1个位置是表头字符第一列同理。中间n-1行、n-1列的区域每个格子都是一个两位字符串表示“行首字符代表的数字 列首字符代表的数字”这个加法结果按某种进制写成两位。我随便构造一个合法的3进制例子4 A B C A AA AB AC B AB AC BA C AC BA BB这个表格里A、B、C三个字符代表的是0、1、2所以这是一个三进制加法表。表格中间“BA”这个字符串就表示结果“10”高位是B低位是A。如果B代表1、A代表0那“BA”就是三进制下的10也就是十进制的3对应213。题目要做的事情就是给定这样一个表让你输出进制数和每个字符对应的数字如果无解输出ERROR。原题里字符可能是数字字符也可能是大写字母所以读的时候不能想当然当成整数。1.2 表头字符数量和进制的关系这是很多新手一上来就懵的地方输入给的是n但进制不是n。因为我们真正能用到的数字字符只有第一行那n-1个比如上面例子n4表头只有A、B、C三个对应的实际数字是0、1、2所以进制是3。换句话说进制 base n - 1。这一点从加法表本质上就能看出来一个base进制的数字系统需要base个不同的数字符号。表头正好列出这base个符号分别是0到base-1的某个排列。第一行第一列的“”只是格式标记不是数字所以字符总数不是n而是n-1。有人会问那中间格子里的两位数高位会不会出现表头里没有的字符不会。因为中间所有结果都是由表头字符代表的数字相加得到的0和1这两个可能作为高位的字符也一定在表头字符集合里。这个结论后面推导定位0和1时会用到。2. 核心规律一行出现几次进位行首字符就是几2.1 为什么两个一位数相加进位最多是1在base进制下表头每个字符代表0到base-1之间的一个数。两个这样的数相加最大是(base-1)(base-1)2*base-2。除以base商最大只能是1不可能出现商为2的情况。举个例子8进制下最大的数字是77714写成8进制是16高位是1低位是6。就算两个数都是当前进制里最大的那个高位也只是1。这个性质是这个题所有规律的根基。因此中间区域每个两位字符串的第一位高位理论上只可能对应两个数字0或者1。也就是说产生了进位高位就是代表1的字符没产生进位高位就是代表0的字符。这里要注意“代表1的字符”不一定叫“1”它可能是A可能是B需要我们先把它找出来。2.2 行首数字的值等于该行高位为1的格子数量现在随便看一行比如行首字符x它代表的数字是v。这一行有n-1个中间格子也就是v去加列头的每个数字列头数字遍历0到base-1。什么时候这一行的结果会产生进位当 v 列值 base 的时候。列头数字排的是一列恰好是0到base-1的一个排列。所以满足 v 列值 base 的列值共有多少个列值可以从base-v开始一直到base-1一共正好v个。这一步非常关键一行中间区域里高位字符等于“1字符”的格子个数恰好等于行首字符代表的数字v。反过来也一样高位等于“0字符”的格子个数就是base - v。用一个具体例子验证。3进制里数字0、1、2对应A、B、C看C这一行C AC BA BBC代表2。C这一行三个结果分别是C加A202三进制是02高位0即AC加B213三进制是10高位1即BC加C224三进制是11高位1即B高位是B的格子有2个C代表的数字正好是2。这个规律的价值在于我们不需要事先知道每个字符对应的数字只要先找到“1字符”然后对每一行数一数有多少个格子的高位等于这个“1字符”就能直接得到该行行首字符的数值。2.3 怎么在一开始就锁定0字符和1字符那怎么在动手之前把0字符和1字符找出来方法就藏在“高位可能出现0或1”这个限制里。统计整个中间区域里每个字符作为高位出现的次数。由于高位只可能是0字符或1字符所以0字符的高位出现次数等于所有“没进位”的格子数量1字符的高位出现次数等于所有“有进位”的格子数量。没有进位和产生进位的组合数量分别是多少把所有行值v按0到base-1枚举当行值为v时没有进位的列值个数是base - v。所以总无进位组合数 base (base-1) ... 1 base*(base1)/2。有进位组合数 0 1 ... (base-1) base*(base-1)/2。所以在所有表头字符中高位出现次数等于 base*(base1)/2 的就是0字符高位出现次数等于 base*(base-1)/2 的就是1字符。由于base最小是2这两个次数不相等可以可靠区分。其他字符的高位出现次数必然为0因为它们代表2到base-1不可能出现在高位。这里也顺带解释了为什么很多错误解法中“统计字符总出现次数”会翻车0字符和2字符在总频次上可能一样多只有单独统计“作为高位出现的次数”才能把它们剥离开。3. 完整实现从读入到输出的每一步3.1 读入表格的正确姿势因为输入里含“”号和一些两位字符串用cin读string是最省事的。int n; cin n; vectorvectorstring a(n, vectorstring(n)); for (int i 0; i n; i) { for (int j 0; j n; j) { cin a[i][j]; } }有人喜欢用getline整行读反而容易踩换行符的坑。这里直接cin string跳过所有空白字符干净利落。“”会被读成一个单独的字符串“”。读完之后表头字符就是第一行从第1列到第n-1列的字符串的首字符int base n - 1; vectorchar head; for (int j 1; j n; j) { head.push_back(a[0][j][0]); }这里a[0][j]是长度为1的字符串取它的[0]就是那个字符。3.2 定位0字符和1字符再计算每个字符的值先统计每个字符作为中间结果“第一位字符”出现的次数mapchar, int highCnt; for (int i 1; i n; i) { for (int j 1; j n; j) { highCnt[a[i][j][0]]; } }然后用前面推导的公式判断0和1char zeroChar 0, oneChar 0; int zeroExpected base * (base 1) / 2; int oneExpected base * (base - 1) / 2; for (char ch : head) { if (highCnt[ch] zeroExpected) zeroChar ch; if (highCnt[ch] oneExpected) oneChar ch; } if (zeroChar 0 || oneChar 0 || zeroChar oneChar) { cout ERROR\n; return 0; }有了1字符之后对每一行数一数高位是一字符的格子数量mapchar, int val; val[zeroChar] 0; for (int i 1; i n; i) { char rowHead a[i][0][0]; int cnt 0; for (int j 1; j n; j) { if (a[i][j][0] oneChar) cnt; } val[rowHead] cnt; if (val[rowHead] 0 || val[rowHead] base) { cout ERROR\n; return 0; } }这一步结束后所有表头字符的数值都已经算出来了。接下来要做的是拿这些数值回到表里验证一遍防止出现自洽但实际不匹配的假解。3.3 验证加法表确保输出前先拦下ERROR验证的逻辑非常简单对于中间每个格子a[i][j]它应该表示行头字符的值 列头字符的值写成base进制的两位字符串高位等于 sum / base低位等于 sum % base。for (int i 1; i n; i) { char rowHead a[i][0][0]; for (int j 1; j n; j) { char colHead a[0][j][0]; string s a[i][j]; if (s.size() ! 2) { cout ERROR\n; return 0; } char hi s[0], lo s[1]; int sum val[rowHead] val[colHead]; int expectHi sum / base; int expectLo sum % base; if (val[hi] ! expectHi || val[lo] ! expectLo) { cout ERROR\n; return 0; } } }注意val[hi]和val[lo]里没有值的话map默认会给0可能导致误判。但合法情况下所有字符都来自表头所以val一定存在。为了更严谨可以改成先判断map里是否存在这里为了简洁先这样写竞赛里没问题。最后输出cout base \n; sort(head.begin(), head.end()); for (char ch : head) { cout ch val[ch] \n; }题目要求按字符顺序输出所以先sort。3.4 可直接参考的完整C代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorvectorstring a(n, vectorstring(n)); for (int i 0; i n; i) { for (int j 0; j n; j) { cin a[i][j]; } } int base n - 1; if (base 2) { cout ERROR\n; return 0; } vectorchar head; for (int j 1; j n; j) { head.push_back(a[0][j][0]); } mapchar, int highCnt; for (int i 1; i n; i) { for (int j 1; j n; j) { highCnt[a[i][j][0]]; } } int zeroExpected base * (base 1) / 2; int oneExpected base * (base - 1) / 2; char zeroChar 0, oneChar 0; for (char ch : head) { if (highCnt[ch] zeroExpected) zeroChar ch; if (highCnt[ch] oneExpected) oneChar ch; } if (zeroChar 0 || oneChar 0 || zeroChar oneChar) { cout ERROR\n; return 0; } mapchar, int val; val[zeroChar] 0; for (int i 1; i n; i) { char rowHead a[i][0][0]; int cnt 0; for (int j 1; j n; j) { if (a[i][j][0] oneChar) cnt; } val[rowHead] cnt; if (val[rowHead] 0 || val[rowHead] base) { cout ERROR\n; return 0; } } for (int i 1; i n; i) { char rowHead a[i][0][0]; for (int j 1; j n; j) { char colHead a[0][j][0]; string s a[i][j]; if (s.size() ! 2) { cout ERROR\n; return 0; } int sum val[rowHead] val[colHead]; int expectHi sum / base; int expectLo sum % base; if (val[s[0]] ! expectHi || val[s[1]] ! expectLo) { cout ERROR\n; return 0; } } } cout base \n; sort(head.begin(), head.end()); for (char ch : head) { cout ch val[ch] \n; } return 0; }这段代码在数据规模不大的情况下n最多10左右完全够用时间复杂度O(n^2)空间O(n^2)。4. 测试验证用手推一遍再说说容易翻的点4.1 用前面的例子推一遍完整流程输入4 A B C A AA AB AC B AB AC BA C AC BA BBn4base3。highCnt统计中间区域9个格子的首位A出现在A行3个、B行前2个、C行第1个共6个正好等于3*4/2。B出现在B行第3个、C行第2和第3个共3个正好等于3*2/2。C出现0次。所以zeroCharAoneCharB。逐行看高位是B的个数A行0个A0。B行1个B1。C行2个C2。验证334三进制是11也就是“BB”表格最后一行最后一个是“BB”一致。输出3 A 0 B 1 C 2这里注意输出的时候字符需要按字典序排不是按输入顺序。如果输入顺序是C、B、A但输出仍要按A、B、C来。4.2 两个容易写错的边界情况第一个是base等于2的情况。n3时两个数字字符一个代表0一个代表1。此时0字符作为高位出现的次数2*(21)/23。1字符作为高位出现的次数2*(2-1)/21。不会有歧义但代码里如果忘了用公式算而是写死“出现次数最多的字符是1”这种直觉判断就会挂。出现次数最多的是0字符不是1。这点千万记住。第二个是输入字符串长度问题。原题中间格子一定是一个两位字符串但如果你用scanf或者getline读很可能因为换行符把某个字符吞掉导致s.size()不为2。我的做法是统一用cin string并且在验证时加一个长度检查遇到不等于2的直接ERROR。竞赛数据虽然不会错但自己造的边界数据跑起来更安心。4.3 关于复杂度这个题其实非常轻中间区域最多就是(n-1)*(n-1)的格子n最多不超过10整个程序跑下来连10万次运算都用不到。所以这个题真正的难点不在性能而在能不能发现“行进位次数等于行首数值”这个规律。一旦规律想通代码反而是所有步骤里最快的。我见过有人拿全排列硬枚举这个题把base个字符对应0到base-1的所有排列都试一遍然后验证加法表。base9时9!大约36万种排列再乘81个格子验证勉强也能过。但那种解法代码长、容易超时、判断ERROR又麻烦不如规律解法干净。5. 常见问题与排查技巧实录5.1 为什么统计字符总出现次数会卡在0和2上这是这个题讨论区里出现频率最高的问题之一。很多人一开始想的是我把中间区域每个字符出现的总次数统计出来次数最高的就是0次高的就是1剩下的只出现固定次数的就是2、3、4……这个思路在部分例子下能用但很容易混淆0和2。原因我前面第二部分已经分析过作为低位个位每个数字出现的次数其实都一样都是base次。0字符和2字符的总频次差异只取决于它们作为高位出现的次数。0字符的高位次数特别大而2字符、3字符这些作为高位根本不该出现所以只看总次数时0和大于等于2的字符完全可能落到同一个频次上。只有把“作为第一位出现”的次数单独拎出来才能把0字符揪出来。调试技巧如果输出结果和样例差得很离谱可以去打印一下highCnt这个map看看每个字符作为高位的次数长什么样。正常情况下你应该看到一个字符的频率等于base*(base1)/2另一个等于base*(base-1)/2其余全是0。如果出现两个字符同时满足同一个期望值那这张表本身就是不合法或者构造有问题的。5.2 字符不在表头里的情况虽然合法数据不会出现但为了代码健壮性我强烈建议在验证阶段养成一个习惯先检查字符在不在val里再取它的值。if (val.find(s[0]) val.end() || val.find(s[1]) val.end()) { cout ERROR\n; return 0; }这样能避免map默认插入0造成的假验证通过。举个例子如果某个中间格子里出现了一个从没在表头见过的神秘字符map默认返回0很可能让程序把错误数据当成合法数据放过去最后输出一个莫名其妙的答案。加一行检查成本极低收益很高。5.3 输出顺序错乱得了部分分有些朋友自己推导出的数字完全正确但输出顺序没按字典序排结果提交上去挂掉。P1013的输出要求是“按字符顺序输出每个字符对应的数字”不是按输入顺序。排序前记得先把head里的字符收集好sort之后再统一输出。调试时如果发现自己手推的结果都对、但评测就是不对优先检查输出格式尤其是字符和数字之间的空格、顺序、大小写。5.4 如果实在看不出规律暴力枚举怎么兜底作为一个竞赛选手有时候在考场上卡住了先用暴力拿分才是王道。P1013的暴力思路是枚举每个字符实际代表的数字范围0到base-1然后用加法表去验证。实现上可以先给表头字符编号然后生成0到base-1的全排列逐个映射验证。base最大9排列数36万验证一次81个格子总共大概3000万次操作在C下其实能过只是写起来不如规律解法简洁。但暴力解法有一个好处当你想验证规律解法对不对时可以写一个暴力程序随机生成若干合法加法表再拿规律解法的结果和暴力结果对比。这是我自己调试时很喜欢用的方式既能增强信心也能快速定位哪一步写错了。6. 写在最后的一点心得P1013这个题我前前后后写过三遍第一遍用字符串模拟硬肝第二遍用全排列碰运气第三遍才真正把“一行的进位次数等于行首数字”这个规律用顺。回头再看这题其实一点不难难的是很多人面对一张表格时第一反应总是去模拟每一位的加法而不是先停下来观察表格整体结构。如果你正在刷题我的建议是遇到这种带表格、带字符映射的题先花三分钟想想“某个字符出现在表格的哪个位置有什么特殊含义”。高位只有0和1、进位次数恰好等于数值这种规律一旦发现代码写出来会非常短而且正确率很高。多积累几条这样的规律以后再做类似“字符谜题”的题会顺手很多。