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

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

題目大意：
給定一個數(shù)字x作為倍數(shù)，給定一個要從1變成的目標(biāo)數(shù)字n。
有兩種操作：
第一種是每次都可以*x；
第二種是在當(dāng)前>10并且最后一位不為0的情況下，把數(shù)字的最后一位提前到第一位來形成一個新的數(shù)字。

問我們從1變成n的最小操作是多少？
如果實在變不成，就輸出-1。

數(shù)據(jù)范圍是在1e6內(nèi)

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

當(dāng)我們面對這種數(shù)據(jù)范圍小的數(shù)字變換的題目時，首先該想的就是能不能爆搜
每次在原數(shù)字的基礎(chǔ)上*x是多一種情況
每次提一下尾部是多一種情況
結(jié)合數(shù)據(jù)范圍較小的情況下來看，我們就可以想到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;//最后一位數(shù)字
	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;
}