[数据结构与算法]洛谷题解 P1037 [NOIP2002 普及组] 产生数（佛洛依德+高精度）

真的好久没有写洛谷的题解，原因就是不会真的好难这个搜索，好多的代码连看都看不明白。干干巴巴的看明白了一个题就连忙发一个题解吧！

链接：
https://www.luogu.com.cn/problem/P1037

题目：

题目就是给你一个数，然后给你一个n对数，代表每一个0到9 的数可以替换成另一个0到9的数，最后求一共能够形成多少种不同数

这个题吧，应该是用搜索来做，救出每一个数可以有几种变形，在根据原来的数求出最后的结果，但是在看题解的时候发现，有一个 Floyd 的算法，索性就看了看感觉还挺简单，刚好我们数据结构刚好学到图论，有刚好有这个Floyd的算法，这种种的巧合，最后选择了这个解法（我的叙述总是感觉怪怪）

思路：

就是用Floyd的算法求出每一个的数他可以变形的个数，在使用高精度求出最后的个数来。（思路简简单单，但是实现课不容易啊）

代码奉上：

首先，我们先看 Floyd 算法来对0~9的每一数进行遍历，看他们每一个数都可以变形的个数。

int n;
cin>>n;
int a,b;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b;//代表a可以变形到b
        arr[a][b]=1;
    }
    for(int k=1;k<10;k++)
        for(int i=0;i<10;i++)
            for(int j=1;j<10;j++)
            if(arr[i][k]&&arr[k][j])
            arr[i][j]=1;
 for(int i=0;i<=9;i++)
    {
        arr[i][i]=1;
        for(int j=0;j<=9;j++)
            if(arr[i][j])
             d[i]++;
    }

（小插曲）写到这里之后我在想会不会会有重复啊，也就是说通过变形之后的值会不会能相同，如果能相同的话这种方法就会有问题了，最后想明白了，可能最后的数会相同但是他们肯定是由不同的数变换来的。 ，不对最后肯定不会相同，正式因为他们是由不同的数变换来的。

最后用d[] 数组来求出每一个数的能够变换的个数来。

解决了这一个之后，最剩下最后一个问题了如何求出数来，按照之前的做法就是对每个数进行遍历然后再乘起来

long long  sum=1;
for(int i=0;i<s.length();i++)
    {
        sum*=d[s[i]-'0'];
    }

但是看题目给的条件，最后得出的数会非常的大，所以我们用long long的类型是根本装不下的，那么我们就想另一种方法啊高精度

int num[101];
 num[1]=1;int len=2;
    for(int i=0;i<s.length();i++)
    {
        for(int j=1;j<=100;j++)
            num[j]*=d[s[i]-'0'];
        for(int j=1;j<=100;j++)
            if(num[j]>=10)
        {num[j+1]+=num[j]/10;num[j]%=10;}
        while (num[len])len++;
        cout<<len<<endl;
    }

刚看到这个代码就感觉啥玩意又/又%的但是一步一步来就很容易理解了，num就是代表每一位的位数，位数到了10进一，len是求这一共几位数。

最后就是完整的代码了

#include<bits/stdc++.h>
#include<iostream>
#define lll __uint128_t
using namespace std;
//inline int read()
//{	int num=0,f=1;char ch=getchar();
//	while(!isalnum(ch)){if(ch=='-')f=-1;ch=getchar();}
//	while(isalnum(ch)){num=num*10+(ch-'0');ch=getchar();}
//	return num*f;}
//template<class T>
//inline void read(T &f) {
//    f = 0; T fu = 1; char c = getchar();
//    while (c < '0' || c > '9') { if (c == '-') { fu = -1; } c = getchar(); }
//    while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }
//    f *= fu;
//}
//int arr[200010],brr[200010],w[200010];
int arr[10][10],d[10];
int num[101];
int main()
{
    string s;
    int n;
    cin>>s>>n;
    int a,b;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b;
        arr[a][b]=1;
    }
    for(int k=1;k<10;k++)
        for(int i=0;i<10;i++)
            for(int j=1;j<10;j++)
            if(arr[i][k]&&arr[k][j])
            arr[i][j]=1;
    for(int i=0;i<=9;i++)
    {
        arr[i][i]=1;
        for(int j=0;j<=9;j++)
            if(arr[i][j])
             d[i]++;
    }
    num[1]=1;int len=2;
    for(int i=0;i<s.length();i++)
    {
        for(int j=1;j<=100;j++)
            num[j]*=d[s[i]-'0'];
        for(int j=1;j<=100;j++)
            if(num[j]>=10)
        {
            num[j+1]+=num[j]/10;
            num[j]%=10;
        }
    }
    for(int i=len-1;i>=1;i--)
        cout<<num[i];
}

值得注意的是这个是按照高位数输出的，很容易理解嘛。12345，1是最高位。

其实这段时间还是比较懒吧，题没怎么做，一个劲的瞎搞一些别的东西（也不算是瞎搞毕竟自己喜欢嘛），写的东西也比较少，其实上一周真的是啥也没干成，做了三次题直接把我心态搞炸了，其实也有点自暴自弃吧，学了这么久成效甚微。最后题解博客就当总结博客充数了，上一周也还有很多想整理的东西（比如说还有两次的题解，图论的其他算法感觉也挺有用的 ），最后也没有整理。也快到考试复习月了，这段时间在突破突破吧。