按低位更重要的顺序给字母分配数字，每次赋值后立刻检查已经能确定的低位列是否满足进位加法，从而提前剪掉大量无效分支。
OJ: luogu
题目 ID: P1092
难度:提高+/省选-
标签:搜索递归剪枝模拟
日期: 2026-06-20 19:45
题意
给出一个 n 进制加法式：
text
第一行
+第二行
=第三行三个数都恰好有 n 位，用前 n 个大写字母表示数字 0..n-1。
相同字母表示相同数字，不同字母表示不同数字。
要求输出 A, B, C, ... 分别对应哪个数字。
思路
先看一个最直观的小数据暴力版本：
cpp
#include <bits/stdc++.h>
using namespace std;
// brute.cpp：小数据全排列解。
// 直接把 A.. 对应的数字全部枚举出来，最后检查整道 n 进制加法是否成立。
// 这个版本最直观，但复杂度是 n!，只适合很小的数据验证。
int n;
string a, b, c;
int value_of[26];
int used_digit[26];
int answer[26];
bool solved = false;
bool check_full() {
int carry = 0;
for (int i = n - 1; i >= 0; i--) {
int x = value_of[a[i] - 'A'];
int y = value_of[b[i] - 'A'];
int z = value_of[c[i] - 'A'];
int sum = x + y + carry;
if (sum % n != z) {
return false;
}
carry = sum / n;
}
return carry == 0;
}
void save_answer() {
for (int i = 0; i < n; i++) {
answer[i] = value_of[i];
}
}
void dfs(int idx) {
if (solved) {
return;
}
if (idx == n) {
if (check_full()) {
save_answer();
solved = true;
}
return;
}
for (int digit = 0; digit < n; digit++) {
if (used_digit[digit]) {
continue;
}
value_of[idx] = digit;
used_digit[digit] = 1;
dfs(idx + 1);
used_digit[digit] = 0;
value_of[idx] = -1;
if (solved) {
return;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> a >> b >> c;
memset(used_digit, 0, sizeof(used_digit));
for (int i = 0; i < 26; i++) {
value_of[i] = -1;
answer[i] = -1;
}
dfs(0);
for (int i = 0; i < n; i++) {
if (i) {
cout << ' ';
}
cout << answer[i];
}
cout << '\n';
return 0;
}brute.cpp 直接枚举所有字母到数字的排列，最后整体验证加法是否成立。
它很好理解，但复杂度是 n!，正式数据肯定不行。
这题真正应该抓住的是“低位决定高位进位”。
所以正式解先按“从低位到高位”的顺序，把低位出现过的字母优先放进搜索序列。
之后做普通的字母赋值 DFS：
- 取出下一个字母；
- 枚举一个还没被使用的数字给它；
- 赋值后立刻检查当前已经能确定的低位列是否还可能成立。
这里最关键的是 check_partial()。
它会从最低位开始模拟当前已经能判断的那些列：
- 如果某一列三个字母都已经有值，就必须立刻满足加法；
- 如果某一列前两项已经有值，结果项还没定，那么这一列需要的结果数字不能已经被占用；
- 一旦遇到还无法判断的更高位，就先停下。
这样做的好处是：
- 低位一旦矛盾，可以立刻回溯；
- 不需要等所有字母都排满后才发现这组映射根本不可能成立。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
int n;
string s1, s2, s3;
int value_of[26]; // 每个字母对应的数字，-1 表示还未确定
int used_digit[26]; // 某个数字是否已经被使用
int order_list[26]; // 搜索字母的顺序
int order_cnt;
int answer[26];
bool solved = false;
void save_answer() {
for (int i = 0; i < n; i++) {
answer[i] = value_of[i];
}
}
// 检查当前已经赋值的一部分，是否仍然可能扩展成合法解。
bool check_partial() {
int carry = 0;
for (int i = n - 1; i >= 0; i--) {
int a = value_of[s1[i] - 'A'];
int b = value_of[s2[i] - 'A'];
int c = value_of[s3[i] - 'A'];
if (a != -1 && b != -1 && c != -1) {
int sum = a + b + carry;
if (sum % n != c) {
return false;
}
carry = sum / n;
continue;
}
// 当前列还没完全确定，但如果前两项和结果都已经知道，也可以继续推进进位。
if (a != -1 && b != -1 && c == -1) {
int sum = a + b + carry;
int need = sum % n;
if (used_digit[need]) {
return false;
}
carry = sum / n;
continue;
}
// 如果当前列无法完全判断，就先停下，让更高位以后再说。
break;
}
return true;
}
void dfs(int idx) {
if (solved) {
return;
}
if (idx == order_cnt) {
int carry = 0;
for (int i = n - 1; i >= 0; i--) {
int a = value_of[s1[i] - 'A'];
int b = value_of[s2[i] - 'A'];
int c = value_of[s3[i] - 'A'];
int sum = a + b + carry;
if (sum % n != c) {
return;
}
carry = sum / n;
}
if (carry == 0) {
save_answer();
solved = true;
}
return;
}
int ch = order_list[idx];
for (int digit = n - 1; digit >= 0; digit--) {
if (used_digit[digit]) {
continue;
}
value_of[ch] = digit;
used_digit[digit] = 1;
if (check_partial()) {
dfs(idx + 1);
}
used_digit[digit] = 0;
value_of[ch] = -1;
if (solved) {
return;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> s1 >> s2 >> s3;
memset(used_digit, 0, sizeof(used_digit));
for (int i = 0; i < 26; i++) {
value_of[i] = -1;
answer[i] = -1;
}
// 从低位到高位收集字母，优先搜索出现在低位的字母。
bool in_order[26];
memset(in_order, 0, sizeof(in_order));
for (int i = n - 1; i >= 0; i--) {
int x = s1[i] - 'A';
int y = s2[i] - 'A';
int z = s3[i] - 'A';
if (!in_order[x]) {
in_order[x] = true;
order_list[order_cnt++] = x;
}
if (!in_order[y]) {
in_order[y] = true;
order_list[order_cnt++] = y;
}
if (!in_order[z]) {
in_order[z] = true;
order_list[order_cnt++] = z;
}
}
dfs(0);
for (int i = 0; i < n; i++) {
if (i) {
cout << ' ';
}
cout << answer[i];
}
cout << '\n';
return 0;
}复杂度
这题本质仍然是搜索题，最坏情况下没有简单的多项式上界。
但正式解会优先处理低位相关字母，并在搜索中不断检查低位列是否已经冲突，
因此实际搜索量远小于朴素的 n! 全排列。
空间复杂度是
总结
这题的关键不在“枚举排列”，而在“尽可能早地利用低位进位约束”。
让低位重要字母先确定，再及时检查当前低位列是否已经矛盾， 搜索量就会明显小很多。