题目描述
所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。
来看一个简单的例子：
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
搜索+剪枝
这道题目其实还是挺友好的虽然作者我自闭了,毕竟比上一道题目好得多,没有什么卡常优化技巧什么的.
剪枝:我们发现这道题目是有很多数学性质的其实纯搜索也可以90分hh
判断我们当前还没有枚举到的列，但是如果有一列3个字母都确定了，但是有无进位都不满足，说明当前的字母顺序错误，直接EXIT.也就是如果我们是枚举ABC的数字是多少的话,那么如果c[x]!=a[x]+b[x] (x为当前这一列) 那么说明我们之前选择的数不对.
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define fir(i,a,b) for(int i=a;i<=b;i++)
const int N=27;
int n,f[N],vis[N],ans[N];
char a[30],b[30],c[30],d[30];
void init()
{
fir(i,1,n)//将字符变成整数
{
a[i]-='A';
b[i]-='A';
c[i]-='A';
}
int cnt=0;
for (int i=n; i; i--)
{
if (!vis[a[i]])//如果这个数还没有归纳进来的话,下面同理
{
d[cnt++]=a[i];
vis[a[i]]=1;
}
if (!vis[b[i]])
{
d[cnt++]=b[i];
vis[b[i]]=1;
}
if (!vis[c[i]])
{
d[cnt++]=c[i];
vis[c[i]]=1;
}
}
}
bool check()
{
int p = 0;
for (int i=n; i>=1; i--)
{
if (f[a[i]]==-1 || f[b[i]]==-1 || f[c[i]]==-1)//如果有一个数字没确定
p=-1;
else
{
if (p==-1)
{
if ((f[a[i]]+f[b[i]])%n==f[c[i]])
p=(f[a[i]]+f[b[i]])/n;
else if ((f[a[i]]+f[b[i]]+1)%n==f[c[i]])
p=(f[a[i]]+f[b[i]]+1)/n;
else
return 1;
}
else
{
if ((f[a[i]]+f[b[i]]+p)%n==f[c[i]])
p=(f[a[i]]+f[b[i]]+p)/n;
else
return 1;
}
}
}
return p == 1? true:false;
}
bool dfs(int x)
{
if (x == n)
{
memcpy(ans, f, sizeof(f));//拷贝函数,具体可以百度.
return true;
}
for (int i = n - 1; i >= 0; i--)//从后到前枚举
{
f[d[x]]=i;
if (vis[i] || check())
continue;
vis[i]=1;
if (dfs(x + 1))
return true;
vis[i]=0;
}
f[d[x]]=-1;
return false;
}
int main()
{
scanf("%d\n%s %s %s",&n,a+1,b+1,c+1);//从第一位开始枚举
init();
memset(vis, 0, sizeof(vis));
memset(f, -1, sizeof(f));//初始化
dfs(0);
fir(i,0,n-1)
printf("%d ", ans[i]);//输出答案
return 0;
}
%%%