ET


私信TA

用户名:wbc

访问量:59291

签 名:

人生苦短,我TM直接py

等  级
排  名 58
经  验 10336
参赛次数 3
文章发表 68
年  龄 0
在职情况 学生
学  校 东北大学
专  业 计算机科学与技术

  自我简介:

自2020起转python了。。。 C++兼容C,所以不要问为什么我所有的提交都是C++的.... 不AC,毋宁死,代码越短越好,思路越清奇越好hhhhhhhh

解题思路:
首先利用弗洛伊德(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 人评分

  评论区