题目描述
所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。
来看一个简单的例子：
43#9865#045
+ 8468#6633
--------------
44445506978
其中#号代表被虫子啃掉的数字。
根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。
现在，我们对问题做两个限制：
首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。
其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。
如果这个算式是N进制的，我们就取英文字母表的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字：但是这N个字母并不一定顺序地代表0到N-1。
输入数据保证N个字母分别至少出现一次。
BADC
+ CBDA
----------
DCCC
上面的算式是一个4进制的算式。
很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。
你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算式成立。
输入数据保证有且仅有一组解。
输入格式
输入包含4行。
第一行有一个正整数N(N<=26)，后面的3行每行有一个由大写字母组成的字符串，分别代表两个加数以及和。
这3个字符串左右两端都没有空格，并且恰好有N位。
输出格式
输出包含一行。
在这一行中，应当包含唯一的那组解。
解是这样表示的：输出N个数字，分别表示A，B，C……所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。
样例
输入样例
5
ABCED
BDACE
EBBAA
输出样例
1 0 3 4 2
算法1
(搜索) $O(n!)$
此题拿到题目，分析题面，是一个非常奇怪的题面，没有什么好的算法来解决，这样就可以去想搜索这个万能的算法了，再反观一波数据范围，因为只有26个英文字母，数据范围很小，就可以基本判定是搜索题了。
确定题目可以用搜索区写以后，就可以来思考一下都有什么问题需要我们去解决。
1. 怎么才能搜到正确的答案
2. 剪枝
首先解决第一个问题，怎么去搜。因为题面说明一个字母只能对应一个数字，所以我们可以得到一个最基础的算法，判断这个数字是否被使用过，如果没有就用，这样是可以不漏的搜出所有情况并求出唯一解。但时间复杂度是一定会超时的。我们得到了最基础的算法，就可以去思考第二个问题，怎么去剪枝。
1.因为题目说明这个只有唯一解，所以发现有问题可以直接回溯，具体问题就是如果任意一位的加数，被加数，和，进位都已知的话，我们就可以判断if((被加数+加数+进位)%n!=和)就说明这个解是有问题的直接回溯。
2.如果进位尚未确定，咱们可以发现这是加法，所以进位只可能为0或1，所以分别进行判断，如果两个都不合法，即可回溯。
3.为了尽量在搜索时让被加数，加数，和已知，我们可以从个位开始搜索。
4.还有一个特判，题目说明和一定为n位，如果在最高位有进位即可回溯。
5.一个小提醒，字符串要用char来存储，不要用string，反正我写的string类型TLE了，可能是我太菜了吧QAQ
参考文献
敬请参考y总讲解视频或题解
C++ 代码
#include<bits/stdc++.h>
using namespace std;
char s[4][30];
int n;
int q[30];
int p[30];
bool v[30];
int tot=0;
bool check()
{
int t=0;
for(int i=n-1;i>=0;i--)
{
int a=p[s[0][i]-'A'],b=p[s[1][i]-'A'],c=p[s[2][i]-'A'];
if(a!=-1&&b!=-1&&c!=-1)
{
if(t==-1)
{
if((a+b)%n!=c&&(a+b+1)%n!=c)
{
return 0;
}
if(!i&&(a+b)>=n)
{
return 0;
}
}
else
{
if((a+b+t)%n!=c)
{
return 0;
}
if(!i&&(a+b+t)>=n)
{
return 0;
}
t=(a+b+t)/n;
}
}
else
{
t=-1;
}
}
return 1;
}
bool dfs(int x)
{
if(x==n)
{
return 1;
}
for(int i=0;i<n;i++)
{
if(!v[i])
{
v[i]=1;
p[q[x]]=i;
if(check()&&dfs(x+1))
{
return 1;
}
v[i]=0;
p[q[x]]=-1;
}
}
return 0;
}
int main()
{
cin>>n;
for(int i=0;i<3;i++)
{
cin>>s[i];
}
for(int j=n-1;j>=0;j--)
{
for(int i=0;i<3;i++)
{
int x=s[i][j]-'A';
if(!v[x])
{
v[x]=1;
q[tot++]=x;
}
}
}
memset(v,0,sizeof(v));
memset(p,-1,sizeof(p));
dfs(0);
for(int i=0;i<n;i++)
cout<<p[i]<<' ';
}
