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

本题的核心在于通过最少的删除操作，使得两个数字之间满足倍数关系（即 是 的倍数，或 是 的倍数）。

约束分析：

• 数据范围： 。 这意味着数字的长度最大仅为 10位 ( 是最小的10位数，最大值接近 )。

• 操作定义： 删除数位。这本质上是在寻找字符串的子序列 (Subsequence)。

• 目标函数： 最小操作次数。

  要使得操作次数最小，等同于要求保留下来的子序列长度之和最大。

算法：子序列枚举与哈希映射

由于数字的最大位数为10，直接暴力搜索的空间非常小，这使得全量枚举（Generate and Check） 成为最稳健且高效的策略。

算法：暴力枚举 结合 哈希去重。

虽然这是一个求“最小代价”的问题，理论上可以使用广度优先搜索 (BFS)。但在本题中，状态空间（所有可能的子数字对）非常有限。直接生成所有可能性并进行两两比对，在逻辑上比维护 BFS 的队列和状态去重更加简单直接，且常数开销更低。

算法可分解为三个主要步骤：

1. 子序列生成 (Subsequence Generation)： 分别生成 和 的所有非空子序列。这里需要通过二进制位掩码（Bitmask）或深度优先搜索（DFS）来遍历每一位是“保留”还是“删除”。

2. 状态压缩与映射 (State Mapping)： 由于不同的删除方式可能产生相同的数值（例如 "101" 删除中间的 '0' 得到 "11"，删除末尾 '1' 得到 "10"，删除首位 '1' 得到 "01" 即数值 1），我们需要记录每个数值对应的最大保留长度。

   • 原因：对于相同的数值结果，保留的字符越多，删除操作越少，代价越低。
   • 数据结构：HashMap<Integer, Integer>，Key 为子序列原本的数值，Value 为该数值对应的最大子序列长度。
   • 注意：关于前导零（如 "01"），在本题逻辑中，如果 "01" 和 "1" 都代表数值 1，但 "01" 长度为 2，"1" 长度为 1，我们显然更倾向于保留 "01" 以减少删除次数。因此，映射时应取由该数值转换来的最大原始长度。

3. 笛卡尔积检测 (Cross-Check)： 遍历 的所有可能数值集合与 的所有可能数值集合，检查整除关系。

   • 条件：x % y == 0 或 y % x == 0。
   • 计算代价：Cost = (LenA - mapA[x]) + (LenB - mapB[y])。
   • 维护全局最小值。

代码实现

#include <bits/stdc++.h>
#include <limits>
#include <unordered_map>
using namespace std;
using ll = long long;

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

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

    auto generate = [](const string & str) -> unordered_map<int, int> {
        int len = str.length();
        unordered_map<int, int> dict;

        for (unsigned int mask = 1; mask < (1 << len); mask++) {
            string subValStr = "";
            for (int i = 0; i < len; i++) {
                if ((mask >> i) & 1) {
                    subValStr += str[i];
                }
            }

            ll subVal = stoll(subValStr);
            int curLen = subValStr.length();
            if (dict.count(subVal) == 0 || curLen > dict[subVal]) {
                dict[subVal] = curLen;
            }
        }

        return dict;
    };

    auto mapA = generate(a);
    auto mapB = generate(b);
    int minOps = numeric_limits<int>::max();

    for (auto [va, la] : mapA) {
        if (va == 0)
            continue;
        for (auto [vb, lb] : mapB) {
            if (vb == 0)
                continue;
            if (va % vb == 0 || vb % va == 0) {
                int curOps = a.length() - la + b.length() - lb;
                minOps = min(minOps, curOps);
            }
        }
    }

    if (minOps == numeric_limits<int>::max())
        minOps = -1;
    cout << minOps << endl;
}