1 条题解
-
0
很巧妙的一个题。
一个比较容易的思路是考虑设 表示 时 的最小数位和，然后发现一点都不好转移。
考虑一个转移方式，任何一个正整数都可以通过 进行 两个操作得到，而这两个操作对数位和的贡献可以随便算，然后直接建边跑边权只有 的最短路就没了。
代码
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int n,dis[N]; deque<int> q; int main(){ scanf("%d",&n); memset(dis,63,sizeof(dis)); dis[1]=1; q.push_back(1); while(!q.empty()){ int x=q.front(); q.pop_front(); if(dis[x*10%n]>dis[x])dis[x*10%n]=dis[x],q.push_front(x*10%n); if(dis[(x+1)%n]>dis[x]+1)dis[(x+1)%n]=dis[x]+1,q.push_back((x+1)%n); } printf("%d",dis[0]); }
- 1
信息
- ID
- 80
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者
-
houzhiyuan