【題解】ZeroJudge d844: NOIP2002 3.产生数

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d844
【解題想法】Floyd-Warshall,大數乘法

  • 這題很雷,WA了好幾次。
  • 關鍵句「經過任意次的變換(0次或多次)」:
    • 【例】如果規則中有 2-> 5 和 5-> 3,就算沒有直接給予 2-> 3 的規則,2-> 3 也要被視為合法的規則。
    • 先定義 a[i][i] = 1 (本身也是一種存在)
    • 利用Floyd-Warshall找出所有 a[i][j], i-> j (0 <= i, j < 10) 的變換可能性。
  • 計算changed[i] = sum(a[i][j]), 0 <= i, j < 10。
  • 定義函式 times():大數乘法 (因為答案可能高達10^30)。
#include <iostream>
#include <cstring>
using namespace std;
int ans[35] = {1};
int a[10][10], changes[10];

void times(int n){
    int carry = 0;
    for (int i = 0; i < 35; i++){
        ans[i] *= n;
        ans[i] += carry;
        carry = ans[i] / 10;
        ans[i] %= 10;
    }
}

int main() {
    int n, b, c, cnt;
    string s;
    memset(a, 0, sizeof(a));
    for (int i = 0; i < 10; i++){
        a[i][i] = 1;
    }
    cin >> s;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> b >> c;
        a[b][ c] = 1;
    }
    for (int i = 0; i < 10; i++){
        for (int j = 0; j < 10; j++){
            for (int k = 0; k < 10; k++){
                if (a[j][k] == 0){
                    if (a[j][i] == 1 && a[i][k] == 1){
                        a[j][k] = 1;
                    }
                }
            }
        }
    }
    for (int i = 0; i < 10; i++){
        cnt = 0;
        for (int j = 0; j < 10; j++){
            if (a[i][j] == 1) cnt++;
        }
        changes[i] = cnt;
    }
    for (int i = 0; i < s.length(); i++){
        times(changes[s[i] - '0']);
    }
    bool flag = false;
    for (int i = 34; i >= 0; i--){
        if (ans[i] != 0) flag = true;
        if (flag) cout << ans[i];
    }
    cout << "\n";
}
分享本文 Share with friends