1 条题解

  • 1
    @ 2021-8-7 21:07:53

    C++ :

    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 30;
    
    int n;
    char eq[3][N];//存储等式
    int q[N];//从低位到高位每个数字的顺序
    int path[N];//存储每个字母对应的是哪个数字
    bool visit[N];
    
    bool check()//剪枝
    {
        for (int i = n - 1, t = 0; i >= 0; i -- )//判断是否合法,从低位开始
        {
            int a = path[eq[0][i] - 'A'], b = path[eq[1][i] - 'A'], c = path[eq[2][i] - 'A'];//分别为被加数,加数,和
            if (a != -1 && b != -1 && c != -1)//非不确定的值
            {
                if (t == -1)//如果t进位不确定
                {
                    if ((a + b) % n != c && (a + b + 1) % n != c) return false;//进位为0且进位为1时都不等于c时,矛盾
                    if (!i && a + b >= n) return false; // 最高位有进位
                }
                else
                {
                    if ((a + b + t) % n != c) return false;//判断当前的t是否合法
                    if (!i && a + b + t >= n) return false;// 最高位有进位
                    t = (a + b + t) / n;//更新进位
                }
            }
            else t = -1;//由于a,b,c有不确定的值,则进位t也不确定
        }
    
        return true;//若没有发现矛盾则继续进行
    }
    
    bool dfs(int u)//u表示当前枚举到哪个数字
    {
        if (u == n) return true;//已经枚举完所有字母了
    
        for (int i = 0; i < n; i ++ )//枚举当前数选哪个数字
            if (!visit[i])//如果这个数字没有被枚举过
            {
                visit[i] = true;
                path[q[u]] = i;//枚举当前数字为i
                if (check() && dfs(u + 1)) return true;//搜下一层,剪枝
                path[q[u]] = -1;//枚举失败,恢复现场
                visit[i] = false;
            }
    
        return false;
    }
    
    int main()
    {
        cin >> n;
        cin >> eq[0] >> eq[1] >> eq[2];//输入三条等式
    
        for (int i = n - 1, k = 0; i >= 0; i -- )//从低位开始
            for (int j = 0; j < 3; j ++ )
            {
                int c = eq[j][i] - 'A';//转换成0 - N-1的数
                if (!visit[c])//若没有被放过的话
                {
                    visit[c] = true;
                    q[k ++ ] = c;//放入每个数字到q中
                }
            }
    
        memset(visit, 0, sizeof visit);//再次初始化访问数组
        memset(path, -1, sizeof path);
    
        dfs(0);
    
        for (int i = 0; i < n; i ++ ) cout << path[i] << ' ';
    
        return 0;
    }
    
    
    • 1

    信息

    ID
    95
    时间
    1000ms
    内存
    128MiB
    难度
    3
    标签
    递交数
    72
    已通过
    40
    上传者