题目描述

blablabla

/*
搜索顺序：依次枚举每个字符对应哪个数字
剪枝：
1.从低位向高位依次考虑每一位：
a，b，c，t
被加数 加数 和 进位
(a+b+t) mod n=c

2.由于和也是n位数 ，因此最高位不可以有进位

3.从最低位开始枚举每个未知数

path[N]每个字母对应的数字
q[N] 从低位到高位字母出现的顺序
st[N] 每个数字有没有被用过
*/

#include<bits/stdc++.h>
using namespace std;
const int N = 30;
char e[3][N];
int n;
int path[N], q[N], st[N];
bool check() {
    int t = 0;
    for (int i = n - 1; i >= 0; i--) {
        int a = path[e[0][i] - 'A'], b = path[e[1][i] - 'A'], c = path[e[2][i] - 'A'];
        if (a != -1 && b != -1 && c != -1) {// a b c 的数值都确定了
            if (t == -1) { //进位不确定 当t=0和t=1都不成立的时候返回false
                if ((a + b) % n != c && (a + b + 1) % n != c)return false;
                if (i == 0 && a + b >= n)return false;//如果最高位有进位返回false
            }
            else {
                if ((a + b + t) % n != c)return false; //t确定的时候
                if (i == 0 && a + b + t >= n)return false;
                t = (a + b + t) / n;//进位为这个
            }
        }//如果a b c 没用都确定 则 进位也不确定 t=-1
        else t = -1;
    }
    return true;
}
//注意 这里dfs定义为bool型 因为要判断每一位是否出错然后剪枝
//如果有一位不成立 则可以终止这条子树的搜索
bool dfs(int u) {
    if (u == n) //从0搜到n-1 u==n的时候全部搜索完毕
        return true;
    for (int i = 0; i < n; i++) { //枚举数字
        if (!st[i]) {
            st[i] = true;
            path[q[u]] = i;//如果这个数字没使用过 赋值给当前最右的字母 q[u]
            if (check() && dfs(u + 1))//如果check没问题dfs下一个 有一位出问题就返回false
                return true;
            else {
                path[q[u]] = -1;//恢复现场
                st[i] = false;
            }
        }
    }
    return false;

}
int main()
{
    cin >> n;
    for (int i = 0; i < 3; i++)
        cin >> e[i];
    int k = 0;
    for (int i = n - 1, k = 0; i >= 0; i--)//从最低位开始枚举三个字符串的对应位
        for (int j = 0; j < 3; j++)
        {
            int c = e[j][i] - 'A';
            if (!st[c])//如果这个字母没标记 这时的st是记录字母是否出现过
            {
                st[c] = true;
                q[k++] = c;//放入队列 记录字母从低到高的出现顺序
            }
        }


    memset(st, 0, sizeof(st)); //将st数组清0 后面的st记录数字是否使用过
    memset(path, -1, sizeof(path));
    dfs(0);
    for (int i = 0; i <= n - 1; i++)
    {
        if (i == n - 1)
            cout << path[i] << endl;
        else cout << path[i] << " ";
    }
    system("PAUSE");
    return 0;
}

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla