当前位置：首页 > ds >正文

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

ds 2025/7/2 6:09:11

文章目录

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

前言

本次训练内容

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

一、题目

给出一个整数 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

样例输出

二、解题思路

这道题目我认为就是高中数学排列组合的一种应用方式，然后因为题中涉及的数目很大，所以需要使用高精度的算法来辅助作答，然后题中的数值“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'];//参考数学排列组合Annfor(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;}
}