临平建设局网站,哈尔滨app开发,关于网站建设工作的通报,软件开发价格标准题目
给出一个整数 n#xff08;n10^30) 和 k 个变换规则#xff08;k15#xff09;。 规则#xff1a; 一位数可变换成另一个一位数#xff1a; 规则的右部不能为零。 例如#xff1a;n234。有规则#xff08;k#xff1d;2#xf…题目
给出一个整数 nn10^30) 和 k 个变换规则k15。 规则 一位数可变换成另一个一位数 规则的右部不能为零。 例如n234。有规则k2 2 5 3 6 上面的整数 234 经过变换后可能产生出的整数为包括原数: 234 534 264 564 共 4 种不同的产生数 问题 给出一个整数 n 和 k 个规则。 求出 经过任意次的变换0次或多次能产生出多少个不同整数。 仅要求输出个数。
输入
键盘输人格式为 n k x1 y1 x2 y2 … … xk yk 234 2 2 5 3 6
输出
一个整数满足条件的个数 4 解题思路
用way[i][j]表示是否可以从数字i变为数字j。然后用Floyd算法计算数字互相转换然后每个数字的方式乘起来要用高精。 代码
#includecstdio
#includecstring
using namespace std;
char s[41];
short a[41];
int k,x,y,way[10][10],n,f[10];
void add(int x)//高精乘
{int g0;for (int i1;i40;i){a[i]a[i]*xg;ga[i]/10;a[i]%10;}
}
void write()//高精输出
{int x40;while (a[x]0) x--;for (int ix;i1;i--) printf(%d,a[i]);
}
int main()
{scanf(%s %d\n,s,k);nstrlen(s);//数字长度for (int i1;ik;i){scanf(%d%d,x,y);way[x][y]true;//表示可以从x变为y}for (int k0;k9;k)for (int i0;i9;i)for (int j0;j9;j)way[i][j](way[i][j] or way[i][k] and way[k][j]);//计算是否可以经过k从i变为jfor (int i0;i9;i){for (int j0;j9;j)if (i!j way[i][j]) f[i];f[i];//计算该数字的变化方式} a[1]1;for (int i0;in;i){add(f[s[i]-48]);//乘}write();//输出
}
