首页 > 代码库 > NOIP2002pj产生数[floyd 高精度]
NOIP2002pj产生数[floyd 高精度]
背景
给出一个整数 n（n<10^30) 和 k 个变换规则（k<=15）。
规则：
一位数可变换成另一个一位数：
规则的右部不能为零。
例如：n=234。有规则（k＝2）：
2－> 5
3－> 6
上面的整数 234 经过变换后可能产生出的整数为（包括原数）:
234
534
264
564
共 4 种不同的产生数
描述
给出一个整数 n 和 k 个规则。
求出：
经过任意次的变换（0次或多次），能产生出多少个不同整数。
仅要求输出个数。格式
输入格式
n k
x1 y1
x2 y2
... ...
xn yn
输出格式
一个整数（满足条件的个数）：
样例1
样例输入1[复制]
234 22 53 6
样例输出1[复制]
4
限制
每个测试点1s
来源
noip2002普及组第三题
－－－－－－－－－－－－－－－－
一个数可以变换多次，floyd求传递闭包(初始化d[i][i]=1)，乘法原理更新答案
要用高精度，注意输出
//// main.cpp// noip2002产生数//// Created by Candy on 9/10/16.// Copyright © 2016 Candy. All rights reserved.//#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;typedef unsigned long long ll;const int N=55,B=1e4;inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}int k,x,y,d[N][N],f[N];char s[N];void floyd(){ for(int i=0;i<=9;i++) d[i][i]=1; for(int k=0;k<=9;k++) for(int i=0;i<=9;i++) for(int j=0;j<=9;j++) d[i][j]=d[i][j]||(d[i][k]&&d[k][j]); for(int i=0;i<=9;i++) for(int j=0;j<=9;j++) if(d[i][j]) f[i]++;}struct big{ int d[100],size; big(){size=1;}} ans;void chengInt(big &a,int k){ int g=0,i; for(i=1;i<=a.size;i++){ int tmp=a.d[i]*k; a.d[i]=(tmp+g)%B; g=(tmp+g)/B; } while(g){ a.d[i++]=g%B; a.size++; g/=B; }}int main(int argc, const char * argv[]) { scanf("%s%d",s,&k); for(int i=1;i<=k;i++) scanf("%d%d",&x,&y),d[x][y]=1; floyd(); ans.d[1]=1; int len=strlen(s); for(int i=0;i<len;i++){ int a=s[i]-‘0‘; chengInt(ans,f[a]); //printf("f %d %d\n",a,f[a]); } for(int i=ans.size;i>=1;i--){ if(i!=ans.size){ if(ans.d[i]<10) cout<<"000"; else if(ans.d[i]<100) cout<<"00"; else if(ans.d[i]<1000) cout<<"0"; } cout<<ans.d[i]; } return 0;}
NOIP2002pj产生数[floyd 高精度]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。