UVa 10782 Send More Money

题目描述

这是一道经典的 字母算术谜题（$\text{Cryptarithmetic Puzzle}$） 题目。题目背景是一个小故事：哥哥为了拖延时间读完一本有趣的书，给弟弟出了一道谜题。这道谜题的形式是，将一个加法算式中的每个数字都用一个大写字母替换，相同的数字用相同的字母替换，不同的数字用不同的字母替换，并且数字不能有前导零。

任务就是给定这样一个被字母替换后的算式（可能不止两个加数），找出每个字母对应的原始数字，使得算式成立。

输入输出格式

输入格式

• 第一行一个整数 $T$（ $T\le 10$ ），表示测试用例的数量。
• 对于每个测试用例：
  • 第一行一个整数 $n$（ $2<n<6$ ），表示算式中的“单词”数量。
  • 第二行包含 $n$ 个由空格分隔的单词，每个单词由 $1$ 到 $10$ 个大写字母组成。最后一个单词是加法的和，其余 $n-1$ 个单词都是加数。

输出格式

• 对于每个测试用例，输出一行，包含所有出现过的字母及其对应的数字。
• 输出格式为 字母=数字，按字母的字典序（A 到 Z）排列，不同字母之间用一个空格分隔。
• 题目保证每个测试用例有且仅有一个解。

约束条件

• 一一映射：每个字母唯一对应一个 $0-9$ 的数字，每个数字最多被一个字母使用。
• 无前导零：每个“单词”（即数字）的首位字母不能对应数字 $0$ ，除非这个单词只有一位。
• 唯一解：题目保证对于给定的输入，存在且只存在一种数字分配方案使得算式成立。

题目分析与解题思路

这道题的本质是一个约束满足问题（$\text{CSP}$）。我们需要为有限个变量（字母）在有限的定义域（$0-9$的数字）内赋值，同时满足一系列约束：

核心思路：回溯搜索（$\text{DFS}$）

最直接的解决方法是回溯算法（$\text{Backtracking}$），也称为深度优先搜索（$\text{DFS}$）。

算法步骤详解

复杂度分析

• 时间复杂度：最坏情况下需要尝试所有字母到数字的排列。设字母个数为 $m$（$m\le 10$），则最坏时间复杂度为 $O(m!)$ 或 $O(10!)$。由于约束较强，实际搜索空间远小于此，并且 $T$ 很小，因此算法可以在时间内通过。
• 空间复杂度：主要是递归栈的深度，为 $O(m)$，以及存储单词和映射的辅助空间，总体空间消耗很小。

代码实现

// Send More Money
// UVa ID: 10782
// Verdict: Accepted
// Submission Date: 2026-01-07
// UVa Run Time: 0.480s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

// 用于存储每个字母对应的数字
int charToDigit[26];
// 用于标记数字是否已被使用
bool digitUsed[10];
// 存储所有出现的字母
vector<char> letters;
// 存储每个单词
vector<string> words;

// 回溯法尝试所有可能的数字映射
bool backtrack(int index) {
// 如果所有字母都已分配数字，进行最终验证
if (index == letters.size()) {
// 检查是否所有单词的首字母不为0（除非单词只有一位）
for (string &word : words)
if (charToDigit[word[0] – 'A'] == 0 && word.size() > 1)
return false;

// 计算所有加数（前n-1个单词）的和
long long sum = 0;
for (int i = 0; i < words.size() – 1; ++i) {
long long num = 0;
for (char c : words[i])
num = num * 10 + charToDigit[c – 'A'];
sum += num;
}

// 计算结果单词（最后一个单词）对应的数字
long long result = 0;
string lastWord = words.back();
for (char c : lastWord)
result = result * 10 + charToDigit[c – 'A'];

// 如果相等，则找到唯一解
return sum == result;
}

char currentChar = letters[index];
// 尝试为当前字母分配0-9中的一个未使用数字
for (int digit = 0; digit <= 9; ++digit) {
// 关键剪枝：如果当前字母是某个单词的首字母且单词长度>1，则不能为0
bool isLeadingZero = false;
if (digit == 0) {
for (string &word : words) {
if (word[0] == currentChar && word.size() > 1) {
isLeadingZero = true;
break;
}
}
}
if (isLeadingZero) continue;

if (!digitUsed[digit]) {
// 尝试赋值
digitUsed[digit] = true;
charToDigit[currentChar – 'A'] = digit;
// 递归为下一个字母赋值
if (backtrack(index + 1))
return true; // 找到解，直接返回
// 回溯，撤销当前选择
digitUsed[digit] = false;
charToDigit[currentChar – 'A'] = –1;
}
}
// 当前字母尝试所有数字都失败，返回上一层
return false;
}

int main() {
int T;
cin >> T;

while (T—) {
int n;
cin >> n;
words.resize(n);
for (int i = 0; i < n; ++i)
cin >> words[i];

// 初始化全局数据结构
fill(charToDigit, charToDigit + 26, –1);
fill(digitUsed, digitUsed + 10, false);
letters.clear();

// 收集所有出现的不同字母
set<char> letterSet;
for (string &word : words)
for (char c : word)
letterSet.insert(c);
// 将set转换为vector，方便按索引访问
letters.assign(letterSet.begin(), letterSet.end());

// 开始回溯搜索
backtrack(0);

// 准备输出：将（字母，数字）对存入向量并按字母排序
vector<pair<char, int>> result;
for (char c : letters)
result.push_back({c, charToDigit[c – 'A']});
sort(result.begin(), result.end());

// 按格式输出结果
for (size_t i = 0; i < result.size(); ++i) {
if (i > 0) cout << ' ';
cout << result[i].first << '=' << result[i].second;
}
cout << '\\n';
}

return 0;
}

代码要点说明：

• 使用 fill 函数初始化数组，简洁高效。
• 利用 set 自动去重和排序的特性来收集字母，再转为 vector 以便进行顺序回溯。
• 在 backtrack 函数中，将“前导零检查”的剪枝提前到了尝试赋值的循环内部，这比在最终验证时才发现失败要高效得多。
• 使用 long long 存储中间计算结果，防止可能的大数溢出。
• 输出时注意格式，字母按字典序排列， = 和数字之间无空格，不同字母对之间有一个空格。

通过这道题，我们不仅练习了回溯算法的经典应用，也学习了如何在搜索中利用问题的具体约束进行有效的剪枝，这是解决许多搜索优化问题的关键技巧。