题解 | #小红的数位删除#

数位删除得到的值是原数值的子序列，只需要生成所有子序列，然后检查即可。

子序列的个数（至多）是，故时间复杂度为，可行.

#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;

using vpii = vector<pair<int, int>>;

vpii subseqSet(int a) {
    auto s =  to_string(a);
    int len = s.size();
    vpii res;

    for (int mask = 1; mask < (1 << len); ++mask) {
        int cur = 0;
        int cnt = 0;

        for (int i = 0; i < len; ++i) {
            if ((mask >> i) & 1) {
                cur = cur * 10 + s[i] - '0';
                cnt++;
            }
        }
        res.push_back({cur, len - cnt});
    }
    return res;
}

int solve(vpii& s1, vpii& s2) {
    int ans = INT_MAX;

    for (auto [v, t1] : s1) {
        for (auto [u, t2] : s2) {
            if (u == 0 || v == 0) {
                if (u == 0 && v == 0) ans = min(ans, t1 + t2);
                continue;
            }

            if (u % v == 0 || v % u == 0)  ans = min(ans, t1 + t2);
        }
    }
    if (ans == INT_MAX) return -1;

    return ans;
}



int main() {
    int a, b;
    cin >> a >> b;
    auto s1 = subseqSet(a);
    auto s2 = subseqSet(b);
    cout << solve(s1, s2);
}
// 64 位输出请用 printf("%lld")