【数据结构入门训练DAY-28】蓝桥杯算法提高VIP-产生数

文章目录

• 前言
• 一、题目
• 二、解题思路
• 结语

前言

本次训练内容

1. 训练高精度乘法。
2. 训练解题思维。

一、题目

 给出一个整数  n 和  k  个变换规则。规则：一位数可变换成另一个一位数：规则的右部不能为零。例如：n=234。有规则（k＝2）：2－>   5 3－>   6
上面的整数  234  经过变换后可能产生出的整数为（包括原数）:
234
534
264
564
共  4  种不同的产生数
问题：
给出一个整数  n  和  k  个规则。
求出：
经过任意次的变换（0次或多次），能产生出多少个不同整数。
仅要求输出个数。

输入格式

n  k 
x1  y1 
x2  y2 
...  ... 

xn  yn 

（n< 10^30) 

（k< =15）

输出格式

一个整数（满足条件的个数）

样例输入

234 2
2 5
3 6

样例输出

4

二、解题思路

        这道题目我认为就是高中数学排列组合的一种应用方式，然后因为题中涉及的数目很大，所以需要使用高精度的算法来辅助作答，然后题中的数值“n”我使用字符串存储。具体代码实现如下：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int temp[10][10];//tag[i][j]=1表示存在i->j的变换
    int d[10000000];
    int p[10000000];
    string n;
    int k;
    while(cin>>n>>k)
    {
        int x,y;
        for(int i=0;i<k;i++)
        {
            cin>>x>>y;
            temp[x][y]=1;
        }

        for(int K=1;K<=9;K++)
            for(int i=0;i<=9;i++)
                for(int j=1;j<=9;j++)
                    if(temp[i][K]&&temp[K][j]) temp[i][j]=1;
        //每个数字可以变换成几种数字形态包括数字本身
        for(int i=0;i<10;i++)
        {
            temp[i][i]=1;
            for(int j=0;j<10;j++)
                if(temp[i][j])
                    d[i]++;
        }
        int z=0;
        p[0]=1;//每个数字的本身
        for(int i=0;n[i];i++)
        {
            z=0;
            int x=d[n[i]-'0'];
            //参考数学排列组合Ann
            for(int i=0;i<500;i++)
            {
                p[i]=(p[i]*x+z);//z是进位数
                z=p[i]/10;
                p[i]%=10;
            }
        }
        int i=500;
        while(p[i]==0) i--;
        for(;i>=0;i--)
        {
            cout<<p[i];
        }
        cout<<endl;
    }
}

总结

  今天的题目我想到了核心的解题思维，但是由于排列组合的思维不知道怎么体现在编码中，还有对高精度知识点掌握的不牢固，导致今天的题目是借鉴了大佬的代码然后自己理解后写出来的，有些惭愧但是也挺开心的，因为又学会了一种解题技巧。