题解 | 小红的数位删除

#include<bits/stdc++.h>
#define inf 0x3fffffff
#define endl '\n'
using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    string sa, sb;
    sa = to_string(a);
    sb = to_string(b);

    int lena = sa.length();
    int lenb = sb.length();

    int ans = inf;
    for (int i = 1; i <= ((1 << lena) - 1); i++) {
        int pa = 0;
        int needa = lena;
        for (int k = 0; k < lena; k++) {
            if ((i >> k) & 1) {
                pa *= 10;
                pa += sa[k] - '0';
                needa--;
            }
        }
        for (int j = 1; j <= ((1 << lenb) - 1); j++) {
            int pb = 0;
            int needb = lenb;
            for (int k = 0; k < lenb; k++) {
                if ((j >> k) & 1) {
                    pb *= 10;
                    pb += sb[k] - '0';
                    needb--;
                }
            }
            //cout << pa << ' ' << pb << ' ' << needa+needb << endl;
            if(pa % pb == 0 || pb % pa == 0) {
                ans = min(ans,needa+needb);
            }
        }
    }

    if(ans == inf) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
}

很简单的状态压缩入门题，只要用位运算枚举每一种状态就好了，注意特判-1的情况，复杂度为2^(len(a)+len(b))，牛客的机子跑的飞快，3ms过