思路分析

• 暴力枚举每一位选哪位数 最坏情况下O(n!)不可取
• 考虑减枝
  • 爆搜最重要的就是顺序，必须保证在一个顺序下能够找到最优解，这里的顺序就是依次从低位到高位进行枚举，因为要处理进位所以这样枚举比较方便，而且一定能找到合法方案。
  • 剪枝一：当前的每一位上的三个数都已经确定的时候，分别设为a, b, c。分两种情况，进位设为t
    • 情况一:t已经确定，那么
      if((a + b + t) % n != c) return false; // 当前位数表示不合法 if(!i && a + b + t >= n)return false;//最后一位还有进位
    • 情况二: t还不确定，那么
      if((a + b + 0) % n != c && (a + b + 1) % n != c)return false;//当前当前无论进位是1还是0都不合法 if(!i && a + b >= n)return false;//最后一位还有进位
    • 如果上述条件都不满足那么就是合法的，加上上面的剪枝效果好很多。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;
const int N = 30;
char e[3][N];
int path[N];
int q[N];
int n;
bool st[N];

bool check()
{
    for(int i = n - 1, t = 0; i >= 0; i --)
    {
        int a = e[0][i] - 'A', b = e[1][i] - 'A', c = e[2][i] - 'A';
        if(path[a] != -1 && path[b] != -1 && path[c] != -1)
        {
            a = path[a], b = path[b], c = path[c];
            if(t != -1)
            {
                if((a + b + t) % n != c)return false;
                if(!i && (a + b + t) >= n)return false;
                t = (a + b + t) / n;
            }
            else
            {
                if((a + b + 1) % n != c && (a + b) % n != c)return false;
                if(!i && (a + b) >= n)return false;
            }
        }
        else t = -1;
    }
    return true;
}

bool dfs(int u)
{
    if(u == n)return true;

    for(int i = 0; i < n; i ++)
        if(!st[i])
        {
            st[i] = true;
            path[q[u]] = i;
            if(check() && dfs(u + 1))return true;
            st[i] = false;
            path[q[u]] = -1;
        }
    return false;
}

int main()
{
    cin >> n;
    for(int i = 0; i < 3; i ++)cin >> e[i];
    for(int i = n - 1, k = 0; i >= 0; i --)
        for(int j = 0; j < 3; j ++)
            if(!st[e[j][i] - 'A'])
            {
                st[e[j][i] - 'A'] = true;
                q[k ++] = e[j][i] - 'A';
            }
    memset(st, 0, sizeof st);
    memset(path, -1, sizeof path);
    dfs(0);

    for(int i = 0; i < n; i ++)cout << path[i] << ' ';

    cout << endl;
    return 0;
}