[NOIP 2002普及组]产生数（floyd+高精度）

https://www.luogu.org/problem/P1037

题目描述

给出一个整数 n（n<10³⁰) 和 k 个变换规则（k<=15）。
规则：
一位数可变换成另一个一位数：规则的右部不能为零。
例如：n=234。有规则（k＝2）：
2－> 5
3－> 6
上面的整数 234 经过变换后可能产生出的整数为（包括原数）:
234
534
264
564
共 4 种不同的产生数
问题：
给出一个整数 n 和 k 个规则。
求出：
经过任意次的变换（0次或多次），能产生出多少个不同整数。仅要求输出个数。

输入描述:

输入格式为：
n k

x₁ y₁

x₂ y₂

... ...

x_n y_n

输出描述:

一个整数（满足条件的个数）

示例1

输入

输出

多给一组数据吧，我第一次写的就这个没过

输入

输出

注意点：

1、一共有15种操作说明一个数可以变成多个不同的数

如果存在 2个操作 a->b b->c 则a既可以变到b也可以变到c

所以可以通过DFS或floyd求出每个数字可以变成多少种数字

2、最多可能有30位数所以最大可能9^30

需要模拟大数乘法而每次乘数有一个不超过10 所以并不难

故floyd+高精度秒杀,用floyd求出每个数字可以变成多少种数字,然后乘起来

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <string>

 #include <math.h>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <math.h>

 const int INF=0x3f3f3f3f;

 typedef long long LL;

 const int mod=1e9+;

 const double PI=acos(-);

 const int maxn=;

 using namespace std;

 //ios::sync_with_stdio(false);

 //    cin.tie(NULL);

 int k;

 char str[];

 int tag[][];//tag[i][j]=1代表数字i可变成j

 int num[];//存放每个数字可变换数字的个数

 int ans[];//答案 

 int main()

 {

     scanf("%s %d",str,&k);

     for(int i=;i<=k;i++)

     {

         int a,b;

         scanf("%d %d",&a,&b);

         tag[a][b]=;

     }

     for(int k=;k<=;k++)//floyd

     {

         for(int i=;i<=;i++)

         {

             for(int j=;j<=;j++)

             {

                 if(tag[i][k]&&tag[k][j])

                     tag[i][j]=;

             }

         }

     }

     for(int i=;i<=;i++)

     {

         tag[i][i]=;

         for(int j=;j<=;j++)

         {

             if(tag[i][j])

                 num[i]++;

         }

     }

     //高精度乘法

     ans[]=;//初始答案

     int jinwei;//进位

     int weishu=;//位数

     for(int i=;str[i];i++)

     {

         jinwei=;

         int x=num[str[i]-''];//该位置数字可变多少种数字

         for(int j=;j<weishu;j++)

         {

             int t=ans[j]*x+jinwei;

             ans[j]=t%;

             jinwei=t/;

         }

         while(jinwei)

         {

             ans[weishu++]=jinwei%;

             jinwei/=;

         }

     }

     for(int i=weishu-;i>=;i--)//注意要反着输出

     {

         printf("%d",ans[i]);

     }

     printf("\n");

     return ;

 }

下面粘另一种写法，主要用了DFS，复杂度可能小一点（from：https://blog.csdn.net/AXuan_K/article/details/41479705）

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 int op[][];

 char str[];

 int vis[];

 int value[];

 int maxlen=;

 void dfs(int a)         //搜索出每个数可以到达的数的个数   用SS保存

 {

     if(vis[a])

         return;

     vis[a]=;

     ss++;

     for(int i=;i<=;i++)

     {

         if(op[a][i]==)

             dfs(i);

     }

 }

 void multiple(int x)             //最大可能 9^30 超long long  所有模拟大数乘法

 {

     int carry=;                 //carry表示进位

     for(int i=;i<=maxlen;i++)

     {

         value[i]=value[i]*x+carry;

             carry=value[i]/;

             value[i]=value[i]%;

     }

     if(carry>)

         value[++maxlen]=carry;

     return;

 }

 int main()

 {

     int m,n,i,j,k;

     int s;

     value[]=;

     memset(op,,sizeof(op));

     scanf("%s%d",str,&k);

     int a,b;

     if(k==)

     {

         cout<<<<endl;

         return ;

     }

     while(k--)

     {

         scanf("%d%d",&a,&b);

         op[a][b]=;               //op[a][b]代表a可以到b

     }

     int len=strlen(str);

     for(i=;i<len;i++)

     {

         memset(vis,,sizeof(vis));

         ss=;

         dfs(str[i]-'');          //求出每位可转换数的乘积   //其实可以用一个数组保存每个数可转换的数的个数

         multiple(ss);

     }

     for(i=maxlen;i>=;i--)

         cout<<value[i];

     cout<<endl;

     return ;

 }

巴特西

[NOIP 2002普及组]产生数（floyd+高精度）

题目描述

输入描述:

输出描述:

示例1

最新文章

热门文章