[数据结构与算法]信息学奥赛一本通 1361：产生数(Produce)

【题目链接】

ybt 1361：产生数(Produce)
本题是简化后的问题，原题为：信息学奥赛一本通 1361：产生数(Produce) | 洛谷 P1037 [NOIP2002 普及组] 产生数
原题整数n的范围为$n<10^{30}$，该题将条件简化，n的范围为$n\le 2000$

【题目考点】

1. 搜索

2. 递推/递归

【解题思路】

解法1：将数字拆分保存在数组中，而后转换每一位

将数字变化规则保存在x、y两个一维数组中，x[i]到y[i]是一种转换规则。
从n的初始值开始搜索，对n做数字拆分，将拆分后的各位数字保存在一个数组中。针对数组中的每位数字，看能否通过转换规则将该数字转换为另一个数字。如果可以，那么做一次转换，将该数组通过数字组合变为一个整数，通过vis数组判断该整数是否出现过。如果出现过，那么略过。如果没出现过，将该整数在vis数组中设为“出现过”，产生的数字个数加1，而后从该整数开始再次进行搜索。

解法2：递推/递归

首先通过搜索，得到每一位数字通过有限次变化后可能变成的数字种类。

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

统计后，得到数字i经过有限次变化后可以变成的数字种类为c[i]。

• 状态定义：记前i位数字可以变换成的数字种类为f[i]，
• 初始状态：f[0] = 1
• 递推关系：前i位数字可以变成的数字种类，为前i-1位数字可以变成的数字种类乘以第i位数字a[i]可以变成的数字种类，即f[i] = f[i-1]*c[a[i]]。

如整数n有ni位，那么f[ni]即为整数n可以变成的数字种类数。
可以用递推或递归的方法来解决该问题。

【题解代码】

解法1：将数字拆分保存在数组中，而后转换每一位

• 深搜

#include <bits/stdc++.h>
using namespace std;
int n, k, x[20], y[20], arr[5], ai, ct;
bool vis[10000];
void toArr(int num)//将整数num进行数字拆分，结果保存在数字数组arr中。（包括num为0的情况） 
{
	ai = 0;
    int a = num;
    do
    {
        arr[++ai] = a % 10;
        a /= 10;
    }while(a > 0);    
}
int toNum()//将数字数组arr保存的数字转为整型数字 
{
    int num = 0;
    for(int i = ai; i >= 1; --i)
        num = num * 10 + arr[i];
    return num;
}
void dfs(int num)
{
    int temp, newNum;
    for(int i = 1; i <= ai; ++i)
    {
        for(int j = 1; j <= k; ++j)//如果存在替换arr[i]的规则 
        {
            if(arr[i] == x[j])
            {
                arr[i] = y[j];
                newNum = toNum();//合成得到新的整数 
                if(vis[newNum] == false)//如果新的整数nweNum没出现过 
                {
                    vis[newNum] = true;//将newNum标记为出现过 
                    ct++;//数字出现的个数加1 
                    dfs(newNum);
                }
                arr[i] = x[j];//还原 
            }
        }
    }
}
int main()
{
    cin >> n >> k;
    for(int i = 1; i <= k; ++i)
        cin >> x[i] >> y[i];
    toArr(n);
    vis[n] = true;
    ct = 1;
    dfs(n);
    cout << ct;
    return 0;
}

• 广搜

#include<bits/stdc++.h>
using namespace std;
#define K 20
int n, k, ct, x[K], y[K], arr[5], ai;
bool vis[10001];
void toArr(int num)//将整数num进行数字拆分，结果保存在数字数组arr中。（包括num为0的情况） 
{
    ai = 0;
    int a = num;
    do
    {
        arr[++ai] = a % 10;
        a /= 10;
    }while(a > 0);    
}
int toNum()//将数字数组arr保存的数字转为整型数字 
{
    int num = 0;
    for(int i = ai; i >= 1; --i)
        num = num * 10 + arr[i];
    return num;
}
void bfs()
{
	queue<int> que;
	vis[n] = true;
	ct = 1;
	que.push(n);
	while(que.empty() == false)
	{
		int u = que.front();
		que.pop();
		toArr(u);//将u转为数字数组arr 
		for(int i = 1; i <= ai; ++i)//遍历arr中的每一位 
		{
			for(int j = 1; j <= k; ++j)//遍历每条规则 
			{
				if(arr[i] == x[j])
				{
					arr[i] = y[j];
					int newNum = toNum();
					if(vis[newNum] == false)
					{
						vis[newNum] = true;
						ct++;
						que.push(newNum);
					}
					arr[i] = x[j];//还原 
				}
			}
		}
	}
}
int main()
{
	cin >> n >> k;
	for(int i = 1; i <= k; ++i)
		cin >> x[i] >> y[i];
	bfs();
	cout << ct;
	return 0;
}

解法2：递推/递归

• 递推

#include<bits/stdc++.h>
using namespace std;
#define K 20
#define N 5
int n, k, c[10], vis[10], a[N], x[K], y[K], f[N];//f[i]：前i位数字可以变换成的数字种类
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()
{
	cin >> n >> k;
	for(int i = 1; i <= k; ++i)
		cin >> x[i] >> y[i];
	init();
	int ni = 0, t = n;//数字n有ni位 
	do//数字拆分，确定数字n的位数，包括n为0的情况 
	{
	    a[++ni] = t % 10;//n的低位到高位第i位数字为a[i] 
	    t /= 10;
    }while(t > 0);
	f[0] = 1;
    for(int i = 1; i <= ni; ++i)
        f[i] = f[i-1] * c[a[i]];
    cout << f[ni];
	return 0;
}

• 递归

#include<bits/stdc++.h>
using namespace std;
#define K 20
#define N 5
int n, k, c[10], vis[10], a[N], x[K], y[K];
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 f(int i)//前i位数字可以变换成的数字种类
{
    if(i == 0)
        return 1;
    return f(i - 1) * c[a[i]];
}
int main()
{
	cin >> n >> k;
	for(int i = 1; i <= k; ++i)
		cin >> x[i] >> y[i];
	init();
	int ni = 0, t = n;//数字n有ni位 
	do//数字拆分，确定数字n的位数，包括n为0的情况 
	{
	    a[++ni] = t % 10;//n的低位到高位第i位数字为a[i] 
	    t /= 10;
    }while(t > 0);
    cout << f(ni);
	return 0;
}