枚举 A~Z 所有可能性的

next_permutation() 50 分

#include <bits/stdc++.h>
using namespace std;
int n;
string s[3];
int num[30]; // 每个字母选了哪个数字
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    cin >> s[0]; // 第一行的式子
    cin >> s[1]; // 第二行的式子
    cin >> s[2]; // 第三行的式子
    // 每个字母转成对应的数字，后面就不用 -'A' 了
    for (int i = 0; i < n; i++)
    {
        s[0][i] -= 'A';
        s[1][i] -= 'A';
        s[2][i] -= 'A';
    }
    // 枚举 A~Z 的所有可能
    for (int i = 0; i <= n - 1; i++)
        num[i] = i;
    do
    {
        // 检查当前等式是否合法
        bool flag = true;
        int add = 0; // 进位
        for (int i = n - 1; i >= 0; i--)
        {
            int now = num[s[0][i]] + num[s[1][i]] + add;
            if (num[s[2][i]] != now % n)
            {
                flag = false;
                break;
            }
            add = now / n;
        }
        if (flag)
        {
            for (int i = 0; i <= n - 1; i++)
                cout << num[i] << " ";
            cout << "\n";
            return 0;
        }
    } while (next_permutation(num, num + n));
    return 0;
}

手写 dfs 暴力枚举 30 分

#include <bits/stdc++.h>
using namespace std;
int n;
string s[3];
int num[30];  // 每个字母选了哪个数字
bool vis[30]; // 每个数字有没有被用过
void dfs(int row, int col)
{
    // 把位置调整到合适位置
    if (row == 3)
    {
        col = col - 1;
        row = 0;
    }
    // 如果每一列都填完了
    if (col == -1)
    {
        // 检查当前等式是否合法
        bool flag = true;
        int add = 0; // 进位
        for (int i = n - 1; i >= 0; i--)
        {
            int now = num[s[0][i]] + num[s[1][i]] + add;
            if (num[s[2][i]] != now % n)
            {
                flag = false;
                break;
            }
            add = now / n;
        }
        if (flag)
        {
            for (int i = 0; i <= n - 1; i++)
                cout << num[i] << " ";
            cout << "\n";
            exit(0);
        }
        return;
    }
    int now = s[row][col]; // 取出当前位置的数字
    if (num[now] == -1)
    {
        // 如果没有被确定过，枚举所有可能性，做下一个位置
        for (int i = 0; i <= n - 1; i++)
            if (!vis[i])
            {
                num[now] = i;
                vis[i] = true;
                dfs(row + 1, col);
                num[now] = -1;
                vis[i] = false;
            }
    }
    else
    {
        // 如果已经被确定了，直接做下一个位置
        dfs(row + 1, col);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    cin >> s[0]; // 第一行的式子
    cin >> s[1]; // 第二行的式子
    cin >> s[2]; // 第三行的式子
    // 每个字母转成对应的数字，后面就不用 -'A' 了
    for (int i = 0; i < n; i++)
    {
        s[0][i] -= 'A';
        s[1][i] -= 'A';
        s[2][i] -= 'A';
    }
    for (int i = 0; i <= n - 1; i++)
    {
        num[i] = -1;    // 每个字母对应的都是没确定
        vis[i] = false; // 每个数字都没被用过
    }
    dfs(0, n - 1); // 从个位开始枚举
    return 0;
}

优化

优化 1：第三行直接算结果（90 分）

#include <bits/stdc++.h>
using namespace std;
int n;
string s[3];
int num[30];  // 每个字母选了哪个数字
bool vis[30]; // 每个数字有没有被用过
int add[30];  // ## 优化 1：每一列的被进位的值
void dfs(int row, int col)
{
    // 如果每一列都填完了，必然合法了
    if (col == -1)
    {

        for (int i = 0; i <= n - 1; i++)
            cout << num[i] << " ";
        cout << "\n";
        exit(0);
    }
    // ## 优化 1：第三行直接计算，不枚举
    if (row == 2)
    {
        int a = num[s[0][col]];
        int b = num[s[1][col]];
        int c = (a + b + add[col]) % n;
        if (num[s[2][col]] == -1)
        {
            // 第三行的字母还没确定的话
            // 不能用 c（c 被用过了） 就不管了
            if (vis[c])
                return;
            // 设置为 c 做下一个位置
            num[s[2][col]] = c;
            vis[c] = true;
            add[col - 1] = (a + b + add[col]) / n;
            dfs(0, col - 1);
            // 还原
            num[s[2][col]] = -1;
            vis[c] = false;
            add[col - 1] = 0;
        }
        else if (num[s[2][col]] == c)
        {
            // 已经确定过了并且正确

            add[col - 1] = (a + b + add[col]) / n;
            dfs(0, col - 1);
            add[col - 1] = 0;
        }
        return;
    }
    int now = s[row][col]; // 取出当前位置的数字
    if (num[now] == -1)
    {
        // 如果没有被确定过，枚举所有可能性，做下一个位置
        for (int i = 0; i <= n - 1; i++)
            if (!vis[i])
            {
                num[now] = i;
                vis[i] = true;
                dfs(row + 1, col);
                num[now] = -1;
                vis[i] = false;
            }
    }
    else
    {
        // 如果已经被确定了，直接做下一个位置
        dfs(row + 1, col);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    cin >> s[0]; // 第一行的式子
    cin >> s[1]; // 第二行的式子
    cin >> s[2]; // 第三行的式子
    // 每个字母转成对应的数字，后面就不用 -'A' 了
    for (int i = 0; i < n; i++)
    {
        s[0][i] -= 'A';
        s[1][i] -= 'A';
        s[2][i] -= 'A';
    }
    for (int i = 0; i <= n - 1; i++)
    {
        num[i] = -1;    // 每个字母对应的都是没确定
        vis[i] = false; // 每个数字都没被用过
    }
    dfs(0, n - 1); // 从个位开始枚举
    return 0;
}

继续优化到满分

又加了点优化

// 基础暴力
#include <bits/stdc++.h>
using namespace std;
int n;
string s[3];
int ans[30]; // 每个数字对应的是多少
// 现在来做第col列，从上往下第 row 个字符，之前已经确定了 cnt 个字符
int num[30];  // 每个数字选了多少
int add[30];  // 每一列的进位
bool vis[30]; // 每个数字有没有被用过
bool flag = false;
void dfs(int col, int row, int cnt)
{
    if (flag)
        return;
    // 优化 2：如果已经确定了 n 个字母了，就直接检查就好了
    if (cnt == n)
    {
        bool flag = true;
        int nowAdd = add[col];
        for (int i = col; i >= 0; i--)
        {
            int now = num[s[0][i]] + num[s[1][i]] + nowAdd;
            if (now % n != num[s[2][i]])
                return;
            nowAdd = now / n;
        }
        for (int i = 0; i < n; i++)
            ans[i] = num[i];
        flag = true;
        return;
    }
    if (col == -1)
    {
        flag = true;
        for (int i = 0; i < n; i++)
            ans[i] = num[i];
        return;
    }
    // 优化 3：每一步都去检查一下有没有可能导致前面的式子答案必然错误
    for (int i = col - 1; i >= 0; i--)
    {
        int d0 = num[s[0][i]];
        int d1 = num[s[1][i]];
        int d2 = num[s[2][i]];
        if (d0 == -1 || d1 == -1 || d2 == -1)
            continue;
        if ((d0 + d1) % n != d2 && (d0 + d1 + 1) % n != d2)
            return;
    }
    if (row == 2)
    {
        int now = num[s[0][col]] + num[s[1][col]] + add[col];
        int d = now % n;
        int s2col = s[2][col];
        if (num[s2col] == -1)
        {
            if (vis[d])
                return;
            num[s2col] = d;
            vis[d] = true;
            add[col - 1] = now / n;
            dfs(col - 1, 0, cnt + 1);
            add[col - 1] = 0;
            vis[d] = false;
            num[s2col] = -1;
        }
        else
        {
            if (d == num[s2col])
            {
                add[col - 1] = now / n;
                dfs(col - 1, 0, cnt);
                add[col - 1] = 0;
            }
        }
        return;
    }
    int now = s[row][col];
    if (num[now] != -1)
    {
        dfs(col, row + 1, cnt);
        return;
    }
    for (int i = 0; i < n; i++)
    {
        if (!vis[i])
        {
            num[now] = i;
            vis[i] = true;
            dfs(col, row + 1, cnt + 1);
            if (flag)
                return;
            num[now] = -1;
            vis[i] = false;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    cin >> s[0];
    cin >> s[1];
    cin >> s[2];
    for (int i = 0; i < n; i++)
    {
        s[0][i] -= 'A';
        s[1][i] -= 'A';
        s[2][i] -= 'A';
    }
    for (int i = 0; i < n; i++)
    {
        num[i] = -1;
        vis[i] = false;
    }
    dfs(n - 1, 0, 0);
    for (int i = 0; i < n; i++)
        cout << ans[i] << " ";
    return 0;
}