ABC 235 D - Multiply and Rotate(bfs)
2022/9/6 23:24:20
本文主要是介绍ABC 235 D - Multiply and Rotate(bfs),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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; }
这篇关于ABC 235 D - Multiply and Rotate(bfs)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-13Slicm 框架怎么进行用户认证?-icode9专业技术文章分享
- 2024-11-13在查询时将 map_coord 列的值转换为字符串有哪些方法?-icode9专业技术文章分享
- 2024-11-13如何将微信地区改成自定义文案?-icode9专业技术文章分享
- 2024-11-13DNS 缓存存在问题有哪些症状和解决方法?-icode9专业技术文章分享
- 2024-11-13HTTP 状态码(405)-Method Not Allowed是什么意思?-icode9专业技术文章分享
- 2024-11-13HTTP 状态码(500)-Internal Server Error是什么意思?-icode9专业技术文章分享
- 2024-11-13在 Element UI 中无法修改 $confirm 的取消按钮文字是什么原因?-icode9专业技术文章分享
- 2024-11-13unity XR是什么?-icode9专业技术文章分享
- 2024-11-13伴随矩阵是什么?-icode9专业技术文章分享
- 2024-11-13怎么使用grep -E 来查找匹配最后 2 条数据?-icode9专业技术文章分享