ACGO巅峰赛#22+题解

解题思路

1. 枚举思路限制：

   • 直接暴力枚举 $a_x, b_x$ 范围是 $[0, 10^9]$，复杂度极大不可行。
   • 需要剪枝或限制搜索空间。

2. 合理限制搜索空间：

   • 题中代码取最大数限制为 $\text{max\_num} = 1000$，即只考虑数字不超过1000的情况（这是为了使枚举可行）。
   • 题目本身未明确说明最大值限制，代码中用1000作为搜索上限，是一种折中方案。

3. 数字合法性检查：

   • 定义函数 $\text{check}(num, set)$，判断数字 $num$ 的每一位是否都属于集合 $set$。

4. 搜索策略（DFS）：

   • 先固定 $a_x$，生成所有由集合 $a$ 组成的数字（长度限制为10位，但实际限制为1000以内）。
   • 对于每个 $a_x$，通过递归枚举所有由集合 $b$ 组成的 $b_x$。
   • 对每个 $a_x, b_x$，计算 $c_x = a_x + b_x$，判断 $c_x$ 是否满足数字集合 $c$ 的要求。
   • 一旦找到满足条件的三元组，输出并终止。

5. 优化：

   • 交换 $a$ 和 $b$，保证枚举的集合较小的一方作为 $a$，减少搜索空间。
   • 递归过程中提前剪枝，避免无效搜索。

---

代码解释

#include <bits/stdc++.h>
using namespace std;

int max_len = 10;
int max_num = 1000;

bool check(int num, const unordered_set<char> &digits) {
    if (num == 0) return digits.count('0') > 0;
    while (num > 0) {
        char ch = (num % 10) + '0';
        if (!digits.count(ch)) return false;
        num /= 10;
    }
    return true;
}

bool gen_b(int x, const vector<char> &digits, int val, int len, const unordered_set<char> &set_c, bool swapped) {
    if (len > 0) {
        int y = val;
        if (y <= max_num) {
            int z = x + y;
            if (z <= max_num && check(z, set_c)) {
                if (swapped) {
                    cout << y << " " << x << " " << z << "\n";
                } else {
                    cout << x << " " << y << " " << z << "\n";
                }
                return true;
            }
        }
    }
    if (len == max_len) return false;

    for (char d : digits) {
        int nd = d - '0';
        if (len == 0 && d == '0') {
            if (gen_b(x, digits, 0, 1, set_c, swapped)) return true;
        } else {
            int nval = val * 10 + nd;
            if (nval <= max_num) {
                if (gen_b(x, digits, nval, len + 1, set_c, swapped)) return true;
            }
        }
    }
    return false;
}

bool gen_a(const vector<char> &digits_a, const vector<char> &digits_b, const unordered_set<char> &set_c, bool swapped, int val = 0, int len = 0) {
    if (len > 0) {
        int x = val;
        if (x <= max_num) {
            if (gen_b(x, digits_b, 0, 0, set_c, swapped)) return true;
        }
    }
    if (len == max_len) return false;

    for (char d : digits_a) {
        int nd = d - '0';
        if (len == 0 && d == '0') {
            if (gen_a(digits_a, digits_b, set_c, swapped, 0, 1)) return true;
        } else {
            int nval = val * 10 + nd;
            if (nval <= max_num) {
                if (gen_a(digits_a, digits_b, set_c, swapped, nval, len + 1)) return true;
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string a, b, c;
    cin >> a >> b >> c;

    unordered_set<char> set_a(a.begin(), a.end()), set_b(b.begin(), b.end()), set_c(c.begin(), c.end());

    bool swapped = false;
    if (set_a.size() > set_b.size()) {
        swap(set_a, set_b);
        swap(a, b);
        swapped = true;
    }

    vector<char> digits_a(set_a.begin(), set_a.end());
    vector<char> digits_b(set_b.begin(), set_b.end());

    sort(digits_a.begin(), digits_a.end());
    sort(digits_b.begin(), digits_b.end());

    if (!gen_a(digits_a, digits_b, set_c, swapped)) {
        cout << "impossible\n";
    }

    return 0;
}