CSP历年复赛题-P1037 [NOIP2002 普及组] 产生数

原题链接：https://www.luogu.com.cn/problem/P1037

题意解读：一个长整数，有若干数字替换规则，计算可以转换成多少种不同的整数。

解题思路：

看题之后，第一感觉，是用DFS：

1、用字符串存储整数

2、用领接表存储数字替换规则，因为一个数字可以替换成多个其他数字

3、在dfs中，枚举字符串每个数字，再枚举规则中每一个可能替换的数字，进行一次替换，继续dfs

隐隐感到不安：30位的整数数量已超过long long，估计要高精度；dfs中对数字判重要借助map，大量的string和dfs可能导致超时、超空间。

不管三七二十一，先写出代码，验证正确性，拿到部分分再说！

40分代码：

#include <bits/stdc++.h>
using namespace std;

vector<int> g[10];
int ans;
unordered_map<string, int> h;

void dfs(string s)
{
    if(h[s]) return;
    ans++;
    h[s] = 1;
    for(int i = 0; i < s.size(); i++)
    {
        for(int j = 0; j < g[s[i] - '0'].size(); j++)
        {
            string tmp(s);
            tmp[i] = g[s[i] - '0'][j] + '0';
            dfs(tmp);
        }
    }
}

int main()
{
    string s;
    int k;
    cin >> s >> k;
    int a, b;
    for(int i = 1; i <= k; i++)
    {
        cin >> a >> b;
        g[a].push_back(b); //加入a->b的规则
    }
    dfs(s);
    cout << ans;

    return 0;
}

进一步思考，对于整数的每一个数字，可以替换成不同的数，例如样例：

234 2
2 5
3 6

对于整数234的每一位，

2：可以选2、5，2种选法

3：可以选3、6，2种选法

4：只能选4，1种选法

根据乘法原理，234一共可以生成2 * 2 * 1 = 4种不同的数

到这里，应该能想到，此题的正解是通过排列组合的乘法原理，统计出每一位一共有多少种选法，相乘即可（由于数据量大，需要高精度*低精度）

现在，问题关键在于如何统计每一个数可以替换成多少个不同的数？

映射规则不仅可以是2 5,3 6，还可以有5 1,1 7等等，因此非常类似于图的遍历，用领接表存储后，从0~9每个数字开始，进行DFS遍历，遍历到的每一个不同的数字个数就是起始数字可以替换的数的个数。

ok，下面暂时不考虑高精度问题，实现代码：

60分代码：

#include <bits/stdc++.h>
using namespace std;

vector<int> g[10];
int r[10]; //0~9可以替换的数的个数
bool h[10]; //hash，标记数是否已经存在
int cnt;
int ans = 1;

//图的遍历，统计从起点能到达的点的个数
void dfs(int i)
{
    if(!h[i]) cnt++;
    h[i] = 1;
    for(int v : g[i])
    {
        if(!h[v]) dfs(v);
    }
}

int main()
{
    string s;
    int k;
    cin >> s >> k;
    int a, b;
    for(int i = 1; i <= k; i++)
    {
        cin >> a >> b;
        g[a].push_back(b); //加入a->b的规则
    }
   
    for(int i = 0; i <= 9; i++)
    {
        memset(h, 0, sizeof(h)); //清0
        cnt = 0; //清0
        dfs(i);
        r[i] = cnt; //保存i可以替换的数的个数
    }
    
    for(int i = 0; i < s.size(); i++)
    {
        ans *= r[s[i] - '0'];
    }
    cout << ans;
    
    return 0;
}

到这里，离AC又进了一步，保持耐心！下面将计算ans *= r[s[i] - '0']的代码修改为高精度乘法~

100分代码：

#include <bits/stdc++.h>
using namespace std;

vector<int> g[10];
int r[10]; //0~9可以替换的数的个数
bool h[10]; //hash，标记数是否已经存在
int cnt;
vector<int> ans(1, 1); //高精度的1

//图的遍历，统计从起点能到达的点的个数
void dfs(int i)
{
    if(!h[i]) cnt++;
    h[i] = 1;
    for(int v : g[i])
    {
        if(!h[v]) dfs(v);
    }
}

//高精度 * 低精度
vector<int> mul(vector<int> a, int b)
{
    vector<int> res;
    int r = 0; //进位
    for(int i = 0; i < a.size(); i++)
    {
        r += a[i] * b;
        res.push_back(r % 10);
        r /= 10;
    }
    while(r)
    {
        res.push_back(r % 10);
        r /= 10;
    }
    return res;
}

int main()
{
    string s;
    int k;
    cin >> s >> k;
    int a, b;
    for(int i = 1; i <= k; i++)
    {
        cin >> a >> b;
        g[a].push_back(b); //加入a->b的规则
    }
   
    for(int i = 0; i <= 9; i++)
    {
        memset(h, 0, sizeof(h)); //清0
        cnt = 0; //清0
        dfs(i);
        r[i] = cnt; //保存i可以替换的数的个数
    }
    
    for(int i = 0; i < s.size(); i++)
    {
        ans = mul(ans, r[s[i] - '0']);
    }
    //高精度，倒序输出
    for(int i = ans.size() - 1; i >= 0; i--)
        cout << ans[i];

    return 0;
}