Informatics Olympiad 1361: Produce

【 Topic link 】

ybt 1361： Generating numbers (Produce)
The original topic is ：
The original question is integer n For the range of $n<10^{30}$, This question simplifies the conditions ,n For the range of $n\le 2000$

【 Topic test site 】

1. Search for

2. Recurrence / recursive

【 Their thinking 】

solution 1： Save the number split in the array , Then convert each bit

Save the number change rule in x、y Two one-dimensional arrays ,x[i] To y[i] Is a transformation rule .
from n Start the search with the initial value of , Yes n Do number splitting , Save the split numbers in an array . For each number in the array , See if you can convert this number to another number by conversion rules . If possible , So do a conversion , Change the array into an integer by combining numbers , adopt vis Array to determine whether the integer has appeared . If there has been , So skip . If it doesn't show up , Place this integer in vis Set to... In the array “ There have been ”, The number of numbers generated plus 1, Then search again from this integer .

solution 2： Recurrence / recursive

First, search , Get the kind of number that each digit may become after a finite number of changes .

Suppose there are rules ：1->2, 1->3, 2->5, 5->1.
So the number 1 After a limited number of changes, it can become 1,2,3,5, common 4 Kind of ;2 After a limited number of changes, it can become ：2,5,1,3, common 4 Kind of .

After statistics , Get figures i The types of numbers that can be changed after a limited number of changes are c[i].

• State definition ： Before recording i The types of digits that can be converted into are f[i],
• The initial state ：f[0] = 1
• Recursive relations ： front i The kind of number that a digit can become , For the former i-1 The kind of number a digit can become multiplied by the number i Digit number a[i] Types of numbers that can be changed , namely f[i] = f[i-1]*c[a[i]].

Such as integers n Yes ni position , that f[ni] Is an integer n The number of types of numbers that can be changed .
This problem can be solved recursively or recursively .

【 Solution code 】

solution 1： Save the number split in the array , Then convert each bit

• Deep search

#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)// The integer num Split numbers , The results are stored in a numeric array arr in .（ Include num by 0 The situation of ） 
{
    
	ai = 0;
    int a = num;
    do
    {
    
        arr[++ai] = a % 10;
        a /= 10;
    }while(a > 0);    
}
int toNum()// Array numbers arr The saved number is converted to an integer number  
{
    
    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)// If there is a replacement arr[i] The rules of  
        {
    
            if(arr[i] == x[j])
            {
    
                arr[i] = y[j];
                newNum = toNum();// Combine to get a new integer  
                if(vis[newNum] == false)// If the new integer nweNum It didn't show up  
                {
    
                    vis[newNum] = true;// take newNum Mark as having occurred  
                    ct++;// The number of digits plus 1 
                    dfs(newNum);
                }
                arr[i] = x[j];// Restore  
            }
        }
    }
}
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;
}

• Guang Shu

#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)// The integer num Split numbers , The results are stored in a numeric array arr in .（ Include num by 0 The situation of ） 
{
    
    ai = 0;
    int a = num;
    do
    {
    
        arr[++ai] = a % 10;
        a /= 10;
    }while(a > 0);    
}
int toNum()// Array numbers arr The saved number is converted to an integer number  
{
    
    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);// take u Convert to a numeric array arr 
		for(int i = 1; i <= ai; ++i)// Traverse arr Every one of you  
		{
    
			for(int j = 1; j <= k; ++j)// Go through each rule  
			{
    
				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];// Restore  
				}
			}
		}
	}
}
int main()
{
    
	cin >> n >> k;
	for(int i = 1; i <= k; ++i)
		cin >> x[i] >> y[i];
	bfs();
	cout << ct;
	return 0;
}

solution 2： Recurrence / recursive

• Recurrence

#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]： front i The kind of number that a digit can be transformed into 
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 Can it be changed into numbers by applying some rules j 
        vis[i] = true;
        dfs(i);// Mark vis 
        for(int j = 0; j <= 9; ++j)// Statistics vis There are several numbers marked in the  
        {
    
            if(vis[j])
                c[i]++;//c[i]: Numbers i The number of numbers that can be changed （ Including myself ） 
        }
    }
}
int main()
{
    
	cin >> n >> k;
	for(int i = 1; i <= k; ++i)
		cin >> x[i] >> y[i];
	init();
	int ni = 0, t = n;// Numbers n Yes ni position  
	do// Digital split , Determine the number n Number of digits , Include n by 0 The situation of  
	{
    
	    a[++ni] = t % 10;//n From low to high i The number of digits is 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;
}

• recursive

#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 Can it be changed into numbers by applying some rules j 
        vis[i] = true;
        dfs(i);// Mark vis 
        for(int j = 0; j <= 9; ++j)// Statistics vis There are several numbers marked in the  
        {
    
            if(vis[j])
                c[i]++;//c[i]: Numbers i The number of numbers that can be changed （ Including myself ） 
        }
    }
}
int f(int i)// front i The kind of number that a digit can be transformed into 
{
    
    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;// Numbers n Yes ni position  
	do// Digital split , Determine the number n Number of digits , Include n by 0 The situation of  
	{
    
	    a[++ni] = t % 10;//n From low to high i The number of digits is a[i] 
	    t /= 10;
    }while(t > 0);
    cout << f(ni);
	return 0;
}