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-22怎么实现ansible playbook 备份代码中命名包含时间戳功能?-icode9专业技术文章分享
- 2024-11-22ansible 的archive 参数是什么意思?-icode9专业技术文章分享
- 2024-11-22ansible 中怎么只用archive 排除某个目录?-icode9专业技术文章分享
- 2024-11-22exclude_path参数是什么作用?-icode9专业技术文章分享
- 2024-11-22微信开放平台第三方平台什么时候调用数据预拉取和数据周期性更新接口?-icode9专业技术文章分享
- 2024-11-22uniapp 实现聊天消息会话的列表功能怎么实现?-icode9专业技术文章分享
- 2024-11-22在Mac系统上将图片中的文字提取出来有哪些方法?-icode9专业技术文章分享
- 2024-11-22excel 表格中怎么固定一行显示不滚动?-icode9专业技术文章分享
- 2024-11-22怎么将 -rwxr-xr-x 修改为 drwxr-xr-x?-icode9专业技术文章分享
- 2024-11-22在Excel中怎么将小数向上取整到最接近的整数?-icode9专业技术文章分享