信息学奥赛一本通 1361：产生数(Produce) | 洛谷 P1037 [NOIP2002 普及组] 产生数

【题目链接】

ybt 1361：产生数(Produce)
洛谷 P1037 [NOIP2002 普及组] 产生数

【题目考点】

1. 动态规划

2. 高精度

【解题思路】

解法1：动态规划

首先通过搜索，得到每一位数字通过有限次变化后可能变成的数字种类。
得到数组c，c[i]表示数字i经过有限次变化后可以变成的数字种类数。

假设有规则：1->2, 1->3, 2->5, 5->1。
那么数字1经过有限次变化后可以成为1,2,3,5，共4种；2经过有限次变化后可以成为：2,5,1,3，共4种。

1. 状态定义

集合：数字n通过给定规则可以变成的数字
限制：只看前几位
统计量：方案数
dp[i]：前i位数字在应用规则经过有限次变化后可以变成的数字种类数。
初始状态：前0位数字的种类数可以认为是1，即dp[0] = 1

2. 状态转移方程

前i位数字通过应用规则可以变成的数字
分割结合：根据第i位数字变成其它数字的情况分割集合
已知第i位数字a[i]可以变为c[a[i]]种数字。
那么前i位数字可以变成的数字种类数，为前i-1位数字可以变成的数字种类数dp[i-1]乘以第i位数字a[i]可以变成的数字种类数c[a[i]]，即dp[i] = dp[i-1]*c[a[i]]。

由于1个数字最多可以变为10个数字（包括变为自己），最多有30位，根据这一状态转移方程，结果可能会是30个10相乘，低精度数字无法表示。因此数字n，状态dp需要用高精度数字来表示，状态转移方程要用到高精乘低精。

【题解代码】

解法1：

#include<bits/stdc++.h>
using namespace std;
#define K 20
#define N 35
struct HPN
{
    int a[N];
    HPN()
    {
        memset(a, 0, sizeof(a));
    }
    HPN(string s)
    {
        memset(a, 0, sizeof(a));
        a[0] = s.length();
        for(int i = 1; i <= a[0]; ++i)
            a[i] = s[a[0]-i] - '0';
    }
    int& operator [] (int i)
    {
        return a[i];
    }
    void setLen(int i)
    {
        while(a[i] == 0 && i > 1)
            i--;
        a[0] = i;
    }
    HPN operator * (int b)//高精乘低精 
    {
        HPN r;
        int c = 0, i;
        for(i = 1; i <= a[0]; ++i)
        {
            r[i] = a[i] * b + c;
            c = r[i] / 10;
            r[i] %= 10; 
        }
        while(c > 0)
        {
            r[i++] = c % 10;
            c /= 10;
        }
        r.setLen(i);
        return r;
    }
    void show()
    {
        for(int i = a[0]; i >= 1; --i)
            cout << a[i];
        cout << endl;
    }
};
int k, c[10], vis[10], x[K], y[K];
HPN dp[N], n;
void dfs(int i)
{
    for(int j = 1; j <= k; ++j)
    {
        if(x[j] == i && vis[y[j]] == false)
        {
            vis[y[j]] = true;
            dfs(y[j]);
        }
    }
}
void init()
{
    for(int i = 0; i <= 9; ++i)
    {
        memset(vis, 0, sizeof(vis));//vis[j]:i能否通过应用某些规则变成数字j 
        vis[i] = true;
        dfs(i);//标记vis 
        for(int j = 0; j <= 9; ++j)//统计vis中有几个数字被标记 
        {
            if(vis[j])
                c[i]++;//c[i]:数字i能变成的数字的个数（包括自己） 
        }
    }
}
int main()
{
    string s;
	cin >> s >> k;
	for(int i = 1; i <= k; ++i)
		cin >> x[i] >> y[i];
	init();
	n = HPN(s);
    dp[0] = HPN("1");
    for(int i = 1; i <= n[0]; ++i)//n[0]为数字n的长度
        dp[i] = dp[i-1] * c[n[i]];
    dp[n[0]].show();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94