企业官网建设流程全解析

洛谷P1013这道题，很多人第一次打开的时候都会愣住：题面给的不是图论模型，也不是排序贪心，而是一张由大写字母组成的加法表。它要求你从这张表里反推出每个字母代表哪个数字，以及这到底是多少进制。乍看像个文字游戏，实际上是一道非常经典的进制与模拟题，考的是从封闭系统里反推参数的能力。这篇文章我会从题目结构讲起，把“数一数两位结果个数”这个关键性质完整推导出来，再给出可提交的C++代码，最后分享我做这道题时踩过的一些边界坑。无论你是刚开始刷普及组题目，还是已经学了一阵想补基础，都可以照着思路自己写一遍。

1. 题目到底在说什么：一张字母加法表

1.1 输入结构长什么样

先看题目给的数据是什么样子。假设输入是这样的：

3 + A B A A B B B BA

第一行的数字3表示整张表的大小，也就是有2个字母参与运算。第一行的开头是加号，后面跟着A、B，这是表头；第一列同样是A、B，每一行的开头是当前行对应的字母。中间的2×2区域就是两个字母相加的结果。

表头里的字母都是单个大写字母，而中间区域的每个结果会用两种形式出现：

• 单个字母，比如A或B，表示一次不进位的加法结果；
• 两个字母组成的串，比如BA，表示一个两位数，是在当前进制下的写法。

为什么这里会冒出“两位数”？因为两个一位数字相加可能超过进制基底。十进制里3加9等于12，写成12就是两位；如果字符A表示数字0，B表示数字1，那么在二进制下1加1等于2，应该写成“10”，也就是串BA。理解这一点是后面所有推理的前提。

1.2 题目要求我们输出什么

如果这张加法表是合法的，我们需要按字母ASCII顺序输出每个字母对应的十进制数字，最后再单独输出进制数。以上面的表为例，推理正确的话，输出应当是这样的形式：

A=0 B=1 2

也就是先输出若干行“字母=数字”，最后一行输出进制。如果这张表自相矛盾，无法还原成任何合法的加法表，就要输出ERROR。

这里有个容易误解的点：题目并不是让你去“算24”或者找规律填字，而是要根据整张表自动恢复字母和数字的一一对应关系，并验证它是否真的能让表内每个格子都成立。

1.3 为什么不能靠肉眼猜

因为字母和数字的对应关系完全未知，而且一张错误表可能乍看起来很整齐。如果只靠眼睛试几个组合，很容易漏掉某个格子对不上的情况。正确的做题姿势是：先通过某个性质快速得到候选映射，再用整张表去自动验证。这个思路贯穿了本文后面所有的内容。

2. 关键性质：数一数“两位结果”，答案就出来了

2.1 两个一位数字相加，最多进到哪一位

在b进制下，任意两个一位数字的取值范围都是0到b-1，它们的和最大是(b-1)+(b-1)，也就是2b-2。

2b-2小于2b，所以这个和除以b得到的商只能是0或1。用生活化的方式理解：就像十进制下两个个位数相加，最大是9加9等于18，永远不会出现19，进位最多是1。

所以在这道题的加法表里，任何一个相加结果都只可能有两种形态：

• 一个字符，说明没有进位；
• 两个字符，说明进位了1。

绝对不可能出现三个字符的结果。这个限制看起来很简单，却是后面“数两位结果个数”方法成立的根本原因。

2.2 站在某个字母的行上观察

现在取出加法表的某一整行来看，比如字母X所在的那一行。这一行的行首固定是X，后面所有格子是X依次与表头其他字母相加的结果。

假设所有字母一共有b个，并且它们恰好代表0到b-1这b个数字。那么这一行里，X实际上和完整的数字集合各相加了一次——相当于拿着一个固定的数，去加0、加1、加2、一直加到b-1。

设X对应数字x。两个一位数相加什么时候会产生进位？条件是x+y≥b。问题是：满足这个条件的y一共有多少个？

y的合法取值一共b个，从0到b-1。满足x+y≥b的y分别是b-x、b-x+1、……、b-1，数一数正好是x个。

结论非常简洁：X这一行里，两位结果的个数，正好等于X所代表的数字x。

2.3 用计数器直接读数字

于是不需要枚举任何映射。读入整张表之后，对每一个行首字母，统计它所在行中间区域里长度为2的结果个数，那个数字就是它代表的数值。

举个例子，如果某一行里出现了3个两位字符串，那么这个行首字母代表的数字就是3。如果某个行首字母对应的数字是0，那么它所在行一次进位都不会有，两位结果个数为0。这不是异常，而是完全正常的。

这个性质把“解未知数”变成了“点人头”，复杂度只有O(b)一次遍历。在字母数量达到9甚至10的情况下，比全排列枚举快了几个数量级。

2.4 为什么数字集合必须是完整的0到b-1

这里有一个隐含前提：字母必须一一对应0到b-1。题目为什么敢这么设定？如果采用更大的进制，比如b个字母却用B进制表示且B大于b，那么加法表中一定会出现一个比b-1更大的数字，但此时已经没有多余字母可以表示它；如果采用更小的进制，又不足以区分b个不同数字。所以合法情况下，进制只能是b=n-1，数字集合只能是0到b-1。

这一点同时也意味着：每一行的两位结果个数不可能超过b-1。如果一个字母统计出来的个数等于b甚至大于b，那么这张表一定不合法，可以直接ERROR。

3. 拿到候选映射后，为什么还要全表验证

3.1 候选映射一定正确吗

计数法给出的映射在绝大多数正常数据里都能直接命中，但题目数据不保证一定是手工构造的合法表，它可能是故意构造的错误表。

一个错误表完全可能满足“每行两位结果个数互不相同，且都落在0到b-1之间”，但具体某个格子对不上。比如某个位置期望结果是串AB，实际输入却是AC；这类错误看不出明显规律，只有逐格验证才能暴露。

所以算法的流程必须是两步：

1. 用计数法快速得到候选映射；
2. 对整张n-1行乘n-1列的加法表逐格核验。

核验全部通过才输出结果，任何一格不一致都输出ERROR。

3.2 验证的具体规则

对每一对表头字母a和c，已经知道val[a]和val[c]，令sum等于这两个数相加，进制为b=n-1，分两种情况：

• 如果sum小于b，期望结果是单个字母，这个字母对应的数字就是sum；
• 如果sum大于等于b，期望结果是两个字母，第一位对应sum除以b的商，第二位对应sum模b的余数。

因为sum最大是2b-2，所以sum除以b的商只可能是1，也就是说进位最高位永远是1；余数则落在0到b-2之间。

把期望串和输入表中的真实串逐位比较，只要有一个不一致，就输出ERROR并结束程序。

3.3 验证前先检查数字集合

在逐格验证之前，还有一个容易忽略的检查：候选数字必须恰好覆盖0到b-1，不能有缺口，也不能重复。

如果两个字母统计出了同一个数字，说明映射不可能是合法的一一对应；如果一个字母统计出的数字等于b或大于b，同样要ERROR。只有保证一一对应，才能建立“数字到字母”的反向数组，否则验证阶段遇到一个数字根本不知道该拼哪个字符，代码很容易写崩。

这个检查虽然简单，但放在统计之后、验证之前，能让后面的逻辑干净很多。

4. 可直接提交的C++实现

4.1 完整代码

下面是我按照这个思路写的版本，读入用cin处理空格，中间结果统一用string保存，避免两位字符串被拆开。注释写在关键位置。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; if (!(cin >> n)) return 0; int b = n - 1; vector<char> sym; string tmp; cin >> tmp; // 读掉 '+' for (int i = 0; i < b; i++) { cin >> tmp; sym.push_back(tmp[0]); } map<char, map<char, string>> table; map<char, int> cnt; for (int i = 0; i < b; i++) { char rowCh; cin >> rowCh; for (int j = 0; j < b; j++) { cin >> tmp; table[rowCh][sym[j]] = tmp; if (tmp.size() == 2) cnt[rowCh]++; } } map<char, int> val; vector<int> used(b + 1, 0); for (char ch : sym) { int d = cnt[ch]; if (d < 0 || d >= b) { cout << "ERROR"; return 0; } val[ch] = d; used[d]++; } for (int d = 0; d < b; d++) { if (used[d] != 1) { cout << "ERROR"; return 0; } } vector<char> inv(b); for (auto &p : val) { inv[p.second] = p.first; } for (char a : sym) { for (char c : sym) { int sum = val[a] + val[c]; string expect; if (sum >= b) { expect.push_back(inv[sum / b]); expect.push_back(inv[sum % b]); } else { expect.push_back(inv[sum]); } if (table[a][c] != expect) { cout << "ERROR"; return 0; } } } for (char ch = 'A'; ch <= 'Z'; ch++) { if (val.count(ch)) { cout << ch << "=" << val[ch] << '\n'; } } cout << b << '\n'; return 0; }

4.2 为什么这样读入

第一行是加号，直接用cin读一个string丢掉就行。后面n-1个字母进入sym数组，记录表头顺序。接着循环n-1次，每次都先读当前行首字母，再连续读n-1个结果字符串。

因为输入格式是每个字符或字符串用空格分隔，cin天然适合这种场景，不需要手动处理换行。

这里最关键的一点是：结果区域必须用string保存，不能用char。如果BA这类两位字符串按char读，会被拆成两个独立字符，整个循环顺序直接错位，后面的表全部乱掉。很多初学者的WA都出在这个地方。

4.3 复杂度分析

整个程序读入需要O(n²)时间，统计每行两位结果数量是O(n)，验证阶段逐格扫描又是O(n²)，输出O(n)。综合复杂度O(n²)，对这个题的数据范围来说绰绰有余。

内存方面，虽然用了二维map存储，但实际上只是b×b个短字符串，总量同样是O(n²)，完全不需要担心。

5. 提交路上容易翻车的几个边界

5.1 不要把第一列统计进去

统计两位结果时，只统计行首字母右侧的n-1个格子，也就是真正的“结果区”。如果循环里不小心把行首字母本身也算了进去，由于行首字母是单个字符，长度不可能为2，在多数样例里不影响结果；但逻辑上不够严谨，而且一旦题目数据形态发生细微变化，这种写法的隐患就会暴露。

规范做法是两层循环都从0到b-1，每一层都对应表头集合，而不是直接遍历整个n×n矩阵。

5.2 输出顺序必须按ASCII，而不是输入顺序

题目要求按字母升序输出。输入第一行可能是B A C，并不以A开头。如果按输入顺序输出，在部分测试点上会得到错误答案。

我代码里是从'A'到'Z'逐一扫描val映射。这样能保证所有字母按字母表顺序出现，同时不会误输出不在表内的其他字母。

5.3 ERROR的大小写不能想当然

不同平台对无解输出的要求不一定完全一致。以洛谷P1013的题面为准，我记得无解时输出ERROR；但如果遇到这个题的变体或迁移版本，最好再仔细读一遍输出说明，可能是ERROR!，也可能是其他标记。

这种一两个字符的细节在比赛中很致命，写代码前先确认，比提交后改要省时间得多。

5.4 n=2这种极限情况

当n=2时，b=1，只有一个字母。它只能代表数字0，加法表只有一格子：0加0等于0。统计法会得到cnt等于0，映射合法，输出该字母等于0，然后输出进制1。

虽然“1进制”在数学讨论里有点别扭，但按题面规则处理没有任何问题。我的代码对这种情况也能正常工作，前提是输入确实满足格式要求。

5.5 不要假设进位的十位一定是字母A

数字1对应的字母完全可能是'Z'或'C'等任意一个表内字母。验证阶段想当然地认为十位一定是'A'，就会在自己构造样例时发现不了问题，一提交就错。

必须通过反向数组inv[sum / b]去取那个代表进位的字母。这也是统计法代码里最值得注意的小细节。

6. 这个题背后的思维方式可以延伸到哪

6.1 换成乘法表，这个技巧还成立吗

两个一位数字相乘最大是(b-1)²。在十进制下是81，两位数；在二进制下是1，一位数；在三进制下是4，写成11_3是两位数；在更大的进制下也基本是两位数甚至更多。

更关键的是，乘法产生的进位不一定是1，商可能大于1。比如9×9等于81，在十进制下商8、余1。这种情况下“数几位结果”不再等于某个数字，题目性质彻底改变。

所以“数位数”这个奇技只在加法模型里成立。它背后的本质是：加法结果长度被两个一位数的和上限限制住，才有了如此简洁的统计量。

6.2 从这道题能学到什么通用经验

常规进制转换题是给你数字和进制，让你输出另一种进制的表示；这道题却是给你一张运算表，让你反推进制和数字。前者是正向映射，后者是逆向推断，思维方式刚好相反。

它教会我一个很好的习惯：面对一个看起来需要搜索枚举的模型，先别急着全排列，静下心在表格结构里找一找不变的统计量。任何一个封闭的运算系统，往往都藏着某个“数个数就能得到答案”的性质。

6.3 我的一点实际操作体会

我第一版代码其实是全排列枚举映射，然后逐格验证，样例能过，但在数据稍微大一点的时候跑得又慢又笨。后来意识到“每行两位结果个数”这个性质，代码瞬间短了很多，思路也清爽了。

从那以后，我做模拟题都会先问自己两个问题：运算结果的长度是否有上限？每一行是否包含完整的数字集合？如果两个答案都是肯定的，那么大概率存在一个简洁的线性统计量等着被发现。洛谷P1013就是这样一个典型案例，值得反复咀嚼。