题解：P1037 [NOIP2002 普及组] 产生数

· · 题解

题解

P1037

题目传送门

题目思路：

  1. 输入处理：读取输入值，包括整数 n 和变换规则。
  2. 图的构建：使用邻接表表示变换规则，其中每个节点（数字）指向它可以变换成的其他节点（数字）。
  3. 可达性计算：对于每个数字（\texttt0\~\texttt9），使用广度优先搜索（BFS）计算所有可达数字。这有助于确定每个数字在经过任意次数变换后可以变换成的数字数量。
  4. 结果计算：将整数 n 转换为字符串，以便逐个处理每个数字。使用高精度乘法方法，将 n 中每个数字的可达数字数量相乘，以处理较大的结果。

AC Code:

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <string>
#include <algorithm>
using namespace std;

string multiply(const string& a, int b) {
    if (b == 0) return "0";
    string res;
    int carry = 0;
    for (int i = a.size() - 1; i >= 0; --i) {
        int product = (a[i] - '0') * b + carry;
        res.push_back(product % 10 + '0');
        carry = product / 10;
    }
    if (carry > 0) {
        res.push_back(carry + '0');
    }
    reverse(res.begin(), res.end());
    size_t start = res.find_first_not_of('0');
    if (start != string::npos) {
        return res.substr(start);
    } else {
        return "0";
    }
}

int main() {
    string n;
    int k;
    cin >> n >> k;

    vector<vector<int>> adj(10);

    for (int i = 0; i < k; ++i) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
    }

    int size[10];
    for (int d = 0; d < 10; ++d) {
        unordered_set<int> visited;
        queue<int> q;
        q.push(d);
        visited.insert(d);

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (int v : adj[u]) {
                if (visited.find(v) == visited.end()) {
                    visited.insert(v);
                    q.push(v);
                }
            }
        }
        size[d] = visited.size();
    }

    string result = "1";
    for (char c : n) {
        int d = c - '0';
        result = multiply(result, size[d]);
    }

    cout << result << endl;

    return 0;
}