Time Limit: 3 second
Memory Limit: 2 MB
【问题描述】
给出一个整数n(n<1030)和m个变换规则(m≤20)。
约定:一个数字可以变换成另一个数字;规则的右部不能为零,即零不能由另一个数字变换而成。这里所说的一个数字就是指一个一位数。
现在给出一个整数n和m个规则,要你求出对n的每一位数字经过任意次的变换(0次或多次),能产生出多少个不同的整数。
例子:
整数123,
有如下的变换规则:
1 2
2 3
那么会产生如下6个不同的整数:
123、223、133、233、323、333
【输入】
共m+2行,第一行是一个不超过30位的整数n,第2行是一个正整数m,接下来的m行是m个变换规则,每一规则是两个数字x、y,中间用一个空格间隔,表示X可以变换成y。
【输出】
一行,表示可以产生的不同整数的个数。
【输入样例】
123
2
1 2
2 3
【输出样例】
6
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=4001
【题解】
平台上只有一组数据,想测更多(4组..)数据可以去这里测评https://vijos.org/p/1129
先处理出每个数字可以直接变出的数字;g[10][10];
然后再用类似floyd的求连通性的做法求出每个数字间接能够变出的数字
for (int k = 0;k <= 9;k++)
for (int i = 0;i <= 9;i++)
for (int j = 0;j <= 9;j++)
if (g[i][k] && g[k][j])
g[i][j] = true;
通过这个g数组可以很容易地处理出每个数字能够变成的不同数字的总数f[i];
根据乘法原理;
答案就是f[n[1]]f[n[2]]….*f[n[len]];
答案要用高精度搞下(单精度乘高精度);
【完整代码】
#include <cstdio>
#include <cstring>
using namespace std;
char n[40];
int m,f[10];
bool g[10][10];
int ans[200];
int main()
{
// freopen("F:\rush.txt","r",stdin);
scanf("%s",n+1);
scanf("%d",&m);
for (int i = 1;i <= m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
g[x][y] = true;
}
for (int k = 0;k <= 9;k++)
for (int i = 0;i <= 9;i++)
for (int j = 0;j <= 9;j++)
if (g[i][k] && g[k][j])
g[i][j] = true;
for (int i = 0;i <= 9;i++)
{
g[i][i] = true;
for (int j = 0;j <= 9;j++)
if (g[i][j])
f[i]++;
}
ans[0] = ans[1] = 1;
int len = strlen(n+1);
for (int i = 1;i <= len;i++)
{
int k = f[n[i]-'0'];
int x = 0;
for (int j = 1;j <= ans[0];j++)
{
ans[j] = ans[j]*k + x;
x = ans[j]/10;
ans[j]%=10;
}
while (x > 0)
{
ans[0]++;
ans[ans[0]] = x;
x = ans[ans[0]]/10;
ans[ans[0]]%=10;
}
}
for (int i = ans[0];i >= 1;i--)
printf("%d",ans[i]);
return 0;
}