[NOIP2002 普及组] 产生数
题目描述
给出一个整数 和
个变换规则。
规则：
- 一位数可变换成另一个一位数。
- 规则的右部不能为零。
例如：。有以下两个规则：
。
。
上面的整数 经过变换后可能产生出的整数为（包括原数）:
。
。
。
。
共 种不同的产生数。
现在给出一个整数 和
个规则。求出经过任意次的变换（
次或多次），能产生出多少个不同整数。
仅要求输出个数。
输入格式
第一行两个整数 ，含义如题面所示。
接下来 行，每行两个整数
，表示每条规则。
输出格式
共一行，输出能生成的数字个数。
样例 #1
样例输入 #1
234 2
2 5
3 6样例输出 #1
4提示
对于 数据，满足
，
。
【题目来源】
NOIP 2002 普及组第三题
#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
#include<cstring>
using namespace std;
map<char,vector<char> >mp;
string st;
int k,l,c[10],mul[100];
void dfs(char th)
{
c[th-'0']=1;
int sz=mp[th].size();
for(int i=0;i<sz;i++)
if(!c[mp[th][i]-'0'])
dfs(mp[th][i]);
}
signed main()
{
cin>>st>>k;
l=st.length();
for(int i=1;i<=k;i++)
{
char x,y;
cin>>x>>y;
mp[x].push_back(y);
}
mul[0]=1;
for(int i=0;i<l;i++)
{
memset(c,0,sizeof(c));
dfs(st[i]);
int sum=0;
for(int i=0;i<=9;i++)
sum+=c[i];
int x=0;
for(int i=0;i<100;i++)
{
mul[i]=mul[i]*sum+x;
x=mul[i]/10;
mul[i]%=10;
}
}
int i=99;
while(i>0&&!mul[i])
i--;
for(;i>=0;i--)
cout<<mul[i];
cout<<endl;
return 0;
}50