B. You Are Given a Decimal String...

╰+哭是因爲堅強的太久メ 2023-06-03 13:51 36阅读 0赞

感觉挺有意思的一道题；

当时看着这题的时候想BB出题人。。。。

自己还是太弱了；

题意：给你一个数字串，问你在相邻两个数字之间最少需要添加几个数字才能使得这个数字串完整；

x-y计数器，就是你每次可以让前一个数字加上x或者y，输出10\*10的计数器，最少需要添加多少次；

看了一下大佬的博客，理解了半天，感觉好强~

转化为最短路来做，每次选择x，y，代表每次可以走x或y的距离，那么可以用弗洛伊德算法处理一下0~9之间的最短路，

再遍历一次数字串，计算每两个数字的最短路，如果走不到就说明在x-y计数器下不能走到，就输出-1；

否者就是全部两两数字之间的和；

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=2e6+10;
    typedef  long long ll;
    const int inf=0x3f3f3f3f;
    int dis[10][10];
    char s[maxn];
    int n;
    int fun(int x,int y){
        memset(dis,inf,sizeof(dis));
        for(int i=0;i<10;i++){
            dis[i][(i+x)%10]=dis[i][(i+y)%10]=1;
        }
        for(int k=0;k<10;k++){
            for(int i=0;i<10;i++){
                for(int j=0;j<10;j++){
                    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
                }
            }
        }
        ll ans=0;
        for(int i=0;i<n-1;i++){
            if(dis[s[i]-'0'][s[i+1]-'0']==inf)
                return -1;
            ans+=dis[s[i]-'0'][s[i+1]-'0']-1;
        }
        return ans;
     
    }
    int main(){
        scanf("%s",s);
        n=strlen(s);
        for(int i=0;i<10;i++){
            for(int j=0;j<10;j++){
                cout<<fun(i,j)<<' ';
            }
            cout<<endl;
        }
     
        return 0;
    }

转载于:https://www.cnblogs.com/lin1874/p/11328609.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/69c536b754544dea84914c69d98686ad.png