题目描述#

所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：

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);
}