题目描述

给定一个由字母组成的等式，其中每一个字母表示一个数字。不同字母表示的数字一定不同。问字母和数字之间是否存在一一对应关系，使得等式成立。若存在多种方案输出按字母顺序排列后字典序最小的解。

比如 SEND+MORE=MONEY 的一个解为 9567+1085=10652。

解题思路

根据题意我们可以得到下面几个条件：

1. 最多只会有10个数字，所以解的组合数不超过 10!=3,628,800
2. 最多允许存在10个字母，否则一定是No Solution
3. 当单词长度超过1时，其首字母肯定不为0

一个简单的解法

首先我们需要将所有字母都找出来，按照字典序排列。再从第一个字母开始按字典序枚举数字，当给每一个字母分配了数字之后，将其带入等式，检查是否相等。

枚举数字时需要注意有的字母不能等于0，这一步我们可以在预处理中完成，用数组notZero表示该字母是否不能为0。

那么可以写出伪代码：

dfs(letter):
    startNum = 0
    If (notZero[ letter ]) Then 
        startNum = 1
    End If
    For i = startNum .. 9
        If not useNum[i] Then
            useNum[i] = true
            val[ letter ] = i
            If letter is last letter Then
                If (check(val)) Then
                    Return True
                End If
            Else 
                If (dfs(next letter)) Then
                    Return True
                End If
            End If
            val[ letter ] = -1
            useNum[i] = false
        End If
    Return False

• val表示每个字母对应的数字，初始化为-1
• useNum表示已经使用了的数字，初始为为false
• check(val)表示将现在的val带入原公式检查是否合法

由于等式长度最大为100，有可能出现两个长度为49的数字进行比较，显然无法正常的采用转化为整数再进行比较的方法。

对于这样的情况，我们有如下的解决方案：

首先将等式右边的单词全部移到左边，这样公式就变成了形如：

word1 + word2 + ... + word4 - word5 - word6 - ... - word8 = 0

举个例子：SEND+MORE-MONEY=0

将其写成笔算的形式

+  SEND
+  MORE
- MONEY
-------
      0

接下来我们从最低位开始，一位一位向高位进行计算。假设前一位的进位为w，则当前位的总和为当前位所有出现过的字母之和加上w。最低位时，因为肯定没有进位，所以w = 0。

每一位的和为：s = D + E - Y + w。

由于我们之前已经枚举出了所有字母表示的数字，因此我们可以直接得到这个和s。

由于我们要使得最后的结果为0，所以s的末尾一定需要为0。

因此判定合法的条件为s % 10 == 0。

若s满足末尾为0，则我们可以继续向高位计算，新的进位为 w = s / 10。

当计算到最高位时，不能产生进位，还需要额外判断s = 0。

伪代码为：

check(val)
    w = 0
    For i = low order .. high order
        s = sigma(digit at order i) + w // val
        If (s % 10 != 0) Then
            Return False
        End If
        If (i == high order && s != 0) Then
            Return False
        End If
        w = s / 10
    End For
    Return True

假设一共出现了m个字母，n种字母。则该算法枚举组合的时间复杂度为 O(10! / (10 - n)!) ~= O(10!)，检查是否合法的时间复杂度为 O(m)，总的时间复杂度为 _O(10!*m)_

对于给定的时间限制肯定是会TLE的，因此我们需要对其进行优化。

优化一

在上面的算法中，我们是按照字母顺序以及字典序开始搜索。总是在枚举完全部的字母后，才进行匹配。然而实际上我们会遇到这样的情况：

比如DCBA+DCCA-DDDA=0，当我们枚举出A的值时，已经可以判定等式最后一位是否能够满足要求。但是在上面的算法中，我们并没有这么做，而是一直在枚举后面的字母。

因此我们提出一个改进的方法，我们按照从低位到高位的过程中，字母出现的顺序去枚举。这样做有一个好处和一个坏处：

好处是，能够在最短时间内检查出是否合法，而不需要去对整个等式进行检查。

坏处是，必须要枚举出所有可能的组合情况，并从中选取字典序最小的情况。

但实际上，由于该方法剪枝的强度比较大，所以对于大多数情况都能够很好的解决。除了一种特殊的情况，这个我们会在优化二中讲到。

该算法的实现要点：

1. 根据笔算公式

   +  SEND
   +  MORE
   - MONEY
   

   从右到左，从上到下，同时计算w和s的值。设最大的位数为m位，一共有n个单词。我们用(i,j)来表示当前枚举到了右起第i位，上起第j个字母。比如在上面例子中(1,1)就是右上角的D，(2,3)就是MONEY中的E。

2. 当枚举到的字母(i,j)尚未赋值时，枚举它可能出现的值；否则直接使用已经枚举的值。
3. 当j = n + 1时，表示该位所有的字母都已经枚举完毕，此时计算w和s并根据结果，决定是否递归计算(i+1,1)。
4. 当i = m + 1时，表示所有位置都已经枚举完毕，此时根据进位的w是否等于0，来判定当前解是否合法。

伪代码实现为：

dfs(i, j, s):
    If (i == m + 1) Then
        If (s == 0) Then
            UpdateAns()
        End If
        Return 
    End If
    If (j == n + 1) Then
        If (s % 10 == 0) Then
            dfs(i + 1, 1, s / 10) // 直接将w加入s
        Else
            Return 
        End If
    End If
    letter = getLetter(i, j)
    If (val[ letter ] != -1) Then
        dfs(i, j + 1, s + val[ letter ] * op[j])
    Else
        startNum = 0
        If (notZero[ letter ]) Then 
            startNum = 1
        End If
        For i = startNum .. 9
            If not useNum[i] Then
                useNum[i] = true
                val[ letter ] = i
                dfs(i, j + 1, s + val[ letter ] * op[j])
                val[ letter ] = -1
                useNum[i] = false
            End If
        End If
    End If

优化二

上面优化搜索顺序之后的代码，能够通过绝大部分的测试点，但是仍然有一种情况没有办法做到。当碰到下面这种形式时，就会超时：

A+B+C+D+E+F+G+HJJJJJJJJJJJJJJ=A+B+C+D+E+F+G+IJJJJJJJJJJJJJJ

超时的原因是因为其中8个字母都在最低位出现了，所以全部进行了枚举。并且只有当计算到最高位时才能确定这两个数是否相等。

对于这种数据，我们仔细观察会发现其中ABCDEFGJ的值实际上无论等于多少都可以，需要注意的只有H和I的值。

举一个简单的例子：A+B+C=AB

由于等式左右两边都有在个位的B，所以B的取值并不会对计算个位的s产生影响。对于这样的字母我们称之为无用的字母。

对于上面那个会超时的例子，我们可以发现，除了H和I以外全部都是无用的字母。枚举他们的值完全是没有必要的，我们只在一个字母出现，并且有用时才去枚举它的值。

因此我们先做一次预处理，将所有无用的字母都标记出，在枚举时直接跳过。

当然这样做还有一个问题：某一种字母每一次出现都是无用的字母，那么当我们找到合法答案时，该字母并没有赋值。

此时我们将剩余的数字按照最小序依次赋值给它们即可。

因此原伪代码改为：

dfs(i, j, s):
    If (i == m + 1) Then
        If (s == 0) Then
            fillAns()   // 赋值剩余的数字
            UpdateAns()
        End If
        Return 
    End If
    If (j == n + 1) Then
        If (s % 10 == 0) Then
            dfs(i + 1, 1, s / 10) // 直接将w加入s
        Else
            Return 
        End If
    End If
    letter = getLetter(i, j) // 若该字母为无用的字母，则返回-1
    If (letter == -1) Then  // 处理无用的字母
        dfs(i, j + 1, s)
        Return ;
    End
    If (val[ letter ] != -1) Then
        dfs(i, j + 1, s + val[ letter ] * op[j])
    Else
        startNum = 0
        If (notZero[ letter ]) Then 
            startNum = 1
        End If
        For i = startNum .. 9
            If not useNum[i] Then
                useNum[i] = true
                val[ letter ] = i
                dfs(i, j + 1, s + val[ letter ] * op[j])
                val[ letter ] = -1
                useNum[i] = false
            End If
        End If
    End If

加上第二种优化之后，就解决特殊情况，也就能够顺利地通过所有的测试点了。

题目总结

本题是一道非常综合的题目，需要在有限的时间里正确实现字符串处理、高精度加减法、深度优先搜索和一些剪枝优化，有不小的难度。 出题者可能也是考虑到本题难度较大，所以在数据设计上没有太为难大家。只要能写出正确的程序，即便没有剪枝优化，也能得到不错的分数。