Description

給出一個整數(shù) n（n<10^30) 和 k 個變換規(guī)則（k<=15）。
　　規(guī)則：
　　　一位數(shù)可變換成另一個一位數(shù)：
　　　規(guī)則的右部不能為零。
　　例如：n=234。有規(guī)則（k＝2）：
　　　　2－> 5
　　　　3－> 6
　　上面的整數(shù) 234 經(jīng)過變換后可能產(chǎn)生出的整數(shù)為（包括原數(shù)）:
　　　234
　　　534
　　　264
　　　564
　　共 4 種不同的產(chǎn)生數(shù)
問題：
　　給出一個整數(shù) n 和 k 個規(guī)則。
求出：
　　經(jīng)過任意次的變換（0次或多次），能產(chǎn)生出多少個不同整數(shù)。
　　僅要求輸出個數(shù)。

Input

n k
x1 y1
x2 y2
… …
xn yn

Output

一個整數(shù)（滿足條件的個數(shù)）：

Sample Input
234 2
2 5
3 6

Sample Output
4
.
.
.
.
.

分析

把被轉(zhuǎn)化的數(shù)設(shè)為一條有向邊的起始點，轉(zhuǎn)化成的數(shù)作為終點，這題很明顯就是要求n數(shù)位上所有數(shù)能達到的點的個數(shù)的乘積 。

但是

我們再看一下數(shù)據(jù)，我們發(fā)現(xiàn)：乘積可能達到10^30！！！
所以，我們要用高精乘
.
.
.
.
.
.

程序：

#include<iostream> using namespace std; int f[10][10]; int k,ans[500]={1},l=1; void wk(int x) {for (int i=0;i<l;i++)ans[i]*=x;for (int i=0;i<l;i++)if (ans[i]>=10){ans[i+1]+=ans[i]/10;ans[i]%=10;}while (ans[l]>0){ans[l+1]=ans[l]/10;ans[l]=ans[l]%10;l++;} } int main() {string s;cin>>s>>k;int x,y,len;int t[10];for (int i=1;i<=k;i++) { cin>>x>>y;f[x][y]=1; }for (int i=0;i<=9;i++)f[i][i]=1;for (int k=1;k<=9;k++) for (int i=0;i<=9;i++)for (int j=1;j<=9;j++)if (f[i][k]==1&&f[k][j]==1) f[i][j]=1;for (int i=0;i<=9;i++){ int tj=0;for (int j=0;j<=9;j++)if (f[i][j]==1) tj++;t[i]=tj;}for (int i=0;i<s.length();i++) wk(t[s[i]-'0']); for (int i=l-1;i>=0;i--) cout<<ans[i];return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9499959.html

總結(jié)

以上是生活随笔為你收集整理的产生数(Floyd)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。