ABC 235 D - Multiply and Rotate（bfs）
2022-09-06 22:34:36

https://atcoder.jp/contests/abc235/tasks/abc235_d

题目大意：
给定一个数字x作为倍数，给定一个要从1变成的目标数字n。
有两种操作：
第一种是每次都可以*x；
第二种是在当前>10并且最后一位不为0的情况下，把数字的最后一位提前到第一位来形成一个新的数字。

问我们从1变成n的最小操作是多少？
如果实在变不成，就输出-1。

数据范围是在1e6内

Sample Input 1  
3 72
Sample Output 1  
4 

Sample Input 2  
2 5
Sample Output 2  
-1 

Sample Input 3  
2 611
Sample Output 3  
12 

Sample Input 4  
2 767090
Sample Output 4  
111

当我们面对这种数据范围小的数字变换的题目时，首先该想的就是能不能爆搜
每次在原数字的基础上*x是多一种情况
每次提一下尾部是多一种情况
结合数据范围较小的情况下来看，我们就可以想到bfs
这个题目的变换部分确实烦啊~

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=2002000,M=2002;
const int INF=0x3f3f3f3f;
LL x,n;
LL dist[N];
bool vis[N];
int cal(LL xx)
{
    if(xx<10||xx%10==0) return 1e8;
    LL y=xx/10;//取到了最后一位之前的
	LL len=log10(xx);
	xx=xx%10;//最后一位数字
	LL num=y+xx*pow(10,len);
	return num;
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    //cin>>T;
    while(T--)
    {
        cin>>x>>n;
        memset(dist,-1,sizeof dist);
        queue<LL> q;
        q.push(1);
        dist[1]=0;
        while(q.size())
        {
            auto t=q.front();
            q.pop();
            if(t==n) break;
            if(t*x<1e6&&dist[t*x]==-1)
            {
                dist[t*x]=dist[t]+1;
                q.push(t*x);
            }
            LL ans=cal(t);
            if(ans<1e6&&dist[ans]==-1)
            {
                dist[ans]=dist[t]+1;
                q.push(ans);
            }
        }
        cout<<dist[n]<<endl;
    }
    return 0;
}