P1013，NOIP 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，对应2+1=3。
题目要做的事情，就是给定这样一个表，让你输出进制数和每个字符对应的数字；如果无解，输出ERROR。原题里字符可能是数字字符，也可能是大写字母，所以读的时候不能想当然当成整数。
1.2 表头字符数量和进制的关系
这是很多新手一上来就懵的地方：输入给的是n，但进制不是n。
因为我们真正能用到的数字字符只有第一行那n-1个，比如上面例子n=4，表头只有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进制下最大的数字是7，7+7=14，写成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加A：2+0=2，三进制是02，高位0，即A
- C加B：2+1=3，三进制是10，高位1，即B
- C加C：2+2=4，三进制是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*(base+1)/2。
- 有进位组合数 = 0 + 1 + ... + (base-1) = base*(base-1)/2。
所以在所有表头字符中，高位出现次数等于 base*(base+1)/2 的，就是0字符；高位出现次数等于 base*(base-1)/2 的，就是1字符。
由于base最小是2，这两个次数不相等，可以可靠区分。其他字符的高位出现次数必然为0，因为它们代表2到base-1，不可能出现在高位。
这里也顺带解释了为什么很多错误解法中“统计字符总出现次数”会翻车：0字符和2字符在总频次上可能一样多，只有单独统计“作为高位出现的次数”，才能把它们剥离开。
3. 完整实现：从读入到输出的每一步
3.1 读入表格的正确姿势
因为输入里含“+”号和一些两位字符串，用cin读string是最省事的。
int n; cin >> n; vector<vector<string>> a(n, vector<string>(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; vector<char> head; for (int j = 1; j < n; j++) { head.push_back(a[0][j][0]); }这里a[0][j]是长度为1的字符串，取它的[0]就是那个字符。
3.2 定位0字符和1字符，再计算每个字符的值
先统计每个字符作为中间结果“第一位字符”出现的次数：
map<char, int> highCnt; for (int i = 1; i < n; i++) { for (int j = 1; j < n; j++) { highCnt[a[i][j][0]]++; } }然后用前面推导的公式判断0和1：
char 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字符之后，对每一行数一数高位是一字符的格子数量：
map<char, 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; vector<vector<string>> a(n, vector<string>(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; } vector<char> head; for (int j = 1; j < n; j++) { head.push_back(a[0][j][0]); } map<char, 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; } map<char, 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 BB- n=4，base=3。
- 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次。
- 所以zeroChar=A，oneChar=B。
- 逐行看高位是B的个数：
- A行：0个，A=0。
- B行：1个，B=1。
- C行：2个，C=2。
- 验证3+3=4，三进制是11，也就是“BB”，表格最后一行最后一个是“BB”，一致。
- 输出：
3 A 0 B 1 C 2这里注意，输出的时候字符需要按字典序排，不是按输入顺序。如果输入顺序是C、B、A，但输出仍要按A、B、C来。
4.2 两个容易写错的边界情况
第一个是base等于2的情况。n=3时，两个数字字符，一个代表0，一个代表1。此时：
- 0字符作为高位出现的次数：2*(2+1)/2=3。
- 1字符作为高位出现的次数：2*(2-1)/2=1。
不会有歧义，但代码里如果忘了用公式算，而是写死“出现次数最多的字符是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的所有排列都试一遍，然后验证加法表。base=9时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*(base+1)/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、进位次数恰好等于数值，这种规律一旦发现，代码写出来会非常短，而且正确率很高。多积累几条这样的规律，以后再做类似“字符谜题”的题会顺手很多。
