解题思路:
首先利用弗洛伊德(Floyd)算法求解数字可以替换的方式并统计每个数字能够替换的种数。。
然后求总共的替换数目。。。
因为最大是10的30次幂,,超出long long int,,需要使用大数进行运算,,这里提供一种避免的方式——利用两个long long int来保存,当一个超过15位数时,把超出部分放入另一个数中,,最后若第二个数不为零,则同时输出两个数即可
hhhhhhhhh好机智。。。
注意事项:
注意两个long long int需要同时进行乘法运算。。
参考代码:
#include <stdio.h> #include <string.h> int main() { int a[10][10] = {0}; int change[10]; char n[100]; long long int ans1, ans2; int k, x, y; int i, j; while (scanf("%s%d", n, &k) != EOF) { for (x = 0; x < 10; x++) { for (y = 0; y < 10; y++) { a[x][y] = 0; } } for (i = 0; i < 10; i++) { a[i][i] = 1; change[i] = 0; } ans1 = 1, ans2 = 0; while (k--) { scanf("%d%d", &x, &y); a[x][y] = 1; } for (x = 0; x < 10; x++) { for (y = 0; y < 10; y++) { if (a[x][y] == 1) for (i = 0; i < 10; i++) { if (a[i][x] == 1) a[i][y] = 1; } } } for (i = 0; i < 10; i++) { for (j = 0; j < 10; j++) { change[i] += a[i][j]; } } for (i = 0; i < strlen(n); i++) { ans1 *= change[n[i] - '0']; ans2 *= change[n[i] - '0']; if (ans1 > 1000000000000000) { ans2 += ans1 / 1000000000000000; ans1 %= 1000000000000000; } } if (ans2 == 0) printf("%lld\n", ans1); else printf("%lld%lld\n", ans2, ans1); } return 0; }
0.0分
7 人评分
C语言程序设计教程(第三版)课后习题6.10 (C语言代码)浏览:1078 |
C语言程序设计教程(第三版)课后习题8.2 (C语言代码)浏览:5259 |
WU-输出九九乘法表 (C++代码)浏览:1838 |
【求[X,Y]内被除3余1并且被除5余3的整数的和】 (C语言代码)浏览:697 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:383 |
矩阵乘方 (C语言代码)浏览:1070 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:706 |
格式化数据输出 (C语言代码)浏览:879 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:489 |
小O的乘积 (C++代码)浏览:784 |