题目描述
所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：
43#98650#45
+ 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
题解
从后向前从大到小倒着搜
分8种情况讨论
打的是真爽
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
char a[30], b[30], c[30];
bool mark[30];
int map[300], n, ans;
void dfs(int pos, int y)
{
ans++;
//printf("%d\n", ans);
if(pos == 0)
{
for (int i = 'A'; i < 'A' + n; i++)
printf("%d ",map[i]);
exit(0);
}
if(map[a[pos]] != -1 && map[b[pos]] != -1 && map[c[pos]] != -1)
{
if((map[a[pos]] + map[b[pos]] + y) % n != map[c[pos]])
return;
else
dfs(pos - 1, (map[a[pos]] + map[b[pos]] + y) / n);
}
else if (map[a[pos]] != -1 && map[b[pos]] != -1)
{
if(mark[(map[a[pos]] + map[b[pos]] + y) % n])
return;
else
{
map[c[pos]] = (map[a[pos]] + map[b[pos]] + y) % n;
mark[(map[a[pos]] + map[b[pos]] + y) % n] = 1;
dfs(pos - 1, (map[a[pos]] + map[b[pos]] + y) / n);
mark[(map[a[pos]] + map[b[pos]] + y) % n] = 0;
map[c[pos]] = -1;
}
}
else if (map[a[pos]] != -1 && map[c[pos]] != -1)
{
int now = map[c[pos]] + n - y - map[a[pos]];
if(mark[now % n])
return;
map[b[pos]] = now % n;
mark[now % n] = 1;
dfs(pos - 1, (now % n) == now ? 1 : 0);
map[b[pos]] = -1;
mark[now % n] = 0;
}
else if (map[b[pos]] != -1 && map[c[pos]] != -1)
{
int now = map[c[pos]] + n - y - map[b[pos]];
if(mark[now % n])
return;
map[a[pos]] = now % n;
mark[now % n] = 1;
dfs(pos - 1, (now % n) == now ? 1 : 0);
map[a[pos]] = -1;
mark[now % n] = 0;
}
else if(map[a[pos]] != -1)
{
for (int i = 0; i < n; i++)
if(!mark[i] && !mark[(map[a[pos]] + i + y) % n])
{
map[b[pos]] = i;
map[c[pos]] = (map[a[pos]] + i + y) % n;
mark[i] = 1;
mark[(map[a[pos]] + i + y) % n] = 1;
dfs(pos - 1, (map[a[pos]] + i + y) / n);
map[b[pos]] = -1;
map[c[pos]] = -1;
mark[i] = 0;
mark[(map[a[pos]] + i + y) % n] = 0;
}
}
else if(map[b[pos]] != -1)
{
for (int i = 0; i < n; i++)
if(!mark[i] && !mark[(map[b[pos]] + i + y) % n])
{
map[a[pos]] = i;
map[c[pos]] = (map[b[pos]] + i + y) % n;
mark[i] = 1;
mark[(map[b[pos]] + i + y) % n] = 1;
dfs(pos - 1, (map[b[pos]] + i + y) / n);
map[a[pos]] = -1;
map[c[pos]] = -1;
mark[i] = 0;
mark[(map[b[pos]] + i + y) % n] = 0;
}
}
else if(map[c[pos]] != -1)
{
for (int i = 0; i < n; i++)
{
if(!mark[i] && !mark[(map[c[pos]] + n - i - y) % n])
{
map[a[pos]] = i;
map[b[pos]] = (map[c[pos]] + n - i - y) % n;
mark[i] = 1;
mark[(map[c[pos]] + n - i - y) % n] = 1;
dfs(pos - 1, ((map[c[pos]] + n - i - y) % n == (map[c[pos]] + n - i - y)));
map[a[pos]] = -1;
map[b[pos]] = -1;
mark[i] = 0;
mark[(map[c[pos]] + n - i - y) % n] = 0;
}
}
}
else
{
// printf("\\\\\n");
for (int i = n - 1; i >= 0; i--)
{
if(mark[i]) continue;
mark[i] = 1;
map[a[pos]] = i;
// printf("------__\n");
for (int j = n - 1; j >= 0; j--)
{
if(!mark[j] && !mark[(i + j + y) % n])
{
// printf("===\n");
mark[j] = mark[(i + j + y) % n] = 1;
map[b[pos]] = j;
map[c[pos]] = (i + j + y) % n;
dfs(pos - 1, (i + j + y) / n);
mark[j] = mark[(i + j + y) % n] = 0;
map[b[pos]] = -1;
map[c[pos]] = -1;
}
else if (mark[j] && mark[(i + j + y) % n] && (j == map[b[pos]]) && ((i + j + y) % n == map[c[pos]]))
{
dfs(pos - 1, (i + j + y) / n);
}
else if (mark[j] && (j == map[b[pos]]) && !mark[(i + j + y) % n])
{
// printf("----\n");
mark[(i + j + y) % n] = 1;
map[c[pos]] = (i + j + y) % n;
dfs(pos - 1, (i + j + y) / n);
map[c[pos]] = -1;
mark[(i + j + y) % n] = 0;
}
}
map[a[pos]] = -1;
mark[i] = 0;
}
}
}
int main()
{
// freopen("alpha.in","r",stdin);
// freopen("alpha.out","w",stdout);
scanf("%d", &n);
scanf("%s%s%s", a + 1, b + 1, c + 1);
for (int i = 'A'; i < 'A' + n; i++)
map[i] = -1;
dfs(n, 0);
}