小红的数位删除【牛客tracker 每日一题】
小红的数位删除
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
小红拿到了两个正整数a aa和b bb，她每次操作可以选择其中一个正整数，删除一个数位。例如，对于" 1243 " "1243""1243"而言，进行一次操作可以生成" 124 " 、 " 123 " 、 " 143 " "124"、"123"、"143""124"、"123"、"143"或" 243 " "243""243"。
小红希望最终a aa是b bb的倍数或者b bb是a aa的倍数。她想知道自己最少的操作次数是多少？
输入描述：
两个正整数a aa和b bb，用空格隔开。
1 ≤ a , b ≤ 10 9 1≤a,b≤10^91≤a,b≤109
输出描述：
如果无法如何都无法使得a aa是b bb的倍数或者b bb是a aa的倍数，则输出− 1 -1−1。
否则输出一个整数，代表小红的最小操作次数。
示例1
输入：
37 111输出：
0说明：
111 111111是37 3737的倍数，所以小红不需要任何操作。
示例2
输入：
1234 99输出：
2说明：
第一个数删除数字′ 1 ′ '1'′1′，变成234 234234。第二个数删除数字′ 9 ′ '9'′9′，变成9 99。234 234234是9 99的倍数。
解题思路
本题采用二进制枚举+暴力验证的思路求解最小操作次数，核心是用二进制位掩码枚举a 、 b a、ba、b所有可能的数位保留/删除组合：将a aa的每一位对应二进制数的一个比特位（1 11保留、0 00删除），同理处理b bb；遍历a aa的所有掩码（共2 n 2^n2n种）和b bb的所有掩码（共2 m 2^m2m种），计算每种组合下保留的数字x xx（a aa的保留数位组成）、y yy（b bb的保留数位组成）及操作次数o p opop（删除的数位总数）；过滤掉x xx或y yy为0 00的无效情况，若x xx是y yy的倍数或y yy是x xx的倍数，则更新最小操作次数a n s ansans；最终若a n s ansans仍为无穷大则输出− 1 -1−1，否则输出a n s ansans。该方法通过枚举所有可能的数位删除组合，暴力验证是否满足倍数条件，虽时间复杂度较高，但因a 、 b a、ba、b位数最多为10 1010位（2 1 0 = 1024 2^10=1024210=1024），实际可高效运行，精准找到满足条件的最小操作次数。
总结
- 核心逻辑是用二进制掩码枚举a 、 b a、ba、b所有数位保留/删除组合，计算对应保留数字和操作次数。
- 关键验证条件：保留数字非0 00且满足倍数关系，更新最小操作次数。
- 最终根据最小操作次数是否为无穷大，输出− 1 -1−1或具体数值。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=2e5+10;constll inf=0x3f3f3f3f3f3f3f3f;intmain(){string a,b;cin>>a>>b;ll ans=inf;ll n=a.size(),m=b.size();for(ll i=0;i<(1<<n);i++){for(ll j=0;j<(1<<m);j++){ll op=0,x=0,y=0;for(ll k=0;k<n;k++){if(i&(1<<k))x=x*10+a[k]-'0';elseop++;}for(ll k=0;k<m;k++){if(j&(1<<k))y=y*10+b[k]-'0';elseop++;}if(!x||!y)continue;if(x%y==0||y%x==0)ans=min(ans,op);}}cout<<(ans==inf?-1:ans)<<endl;return0;}