【NOIP普及组】产生数

💐The Begin💐点点关注，收藏不迷路💐

给出一个整数 n（n<10^30) 和 k 个变换规则（k<=15）。

规则：
一位数可变换成另一个一位数：
规则的右部不能为零。
例如：n=234。有规则（k＝2）：
2－> 5
3－> 6

上面的整数 234 经过变换后可能产生出的整数为（包括原数）:
234
534
264
564
共 4 种不同的产生数

问题：

给出一个整数 n 和 k 个规则。

求出：

经过任意次的变换（0次或多次），能产生出多少个不同整数。
仅要求输出个数。

输入

键盘输人，格式为：
　　n k
　　x1 y1
　　x2 y2
　　… …
　　xn yn

输出

一个整数（满足条件的个数）

样例输入

234 2
2 5
3 6

样例输出

4

C 语言实现：

#include <stdio.h>
#include <string.h>
#include <stdbool.h>// 全局变量定义
char inputStr[33];
int digits[33];
int ruleCounts[33];
int rules[33][16];
int totalRules;
int ruleCountForCurrentDigit;
bool used[10];
long long result[33];// 深度优先搜索函数，判断一个数字的转化规则
void dfs(int x, int y) {// 如果 y 已经被使用过，直接返回if (used[y]) return;used[x] = true;ruleCountForCurrentDigit++;// 递归处理 y 的转化规则for (int i = 1; i <= ruleCounts[y]; i++) {dfs(y, rules[y][i]);}used[x] = false;
}// 处理高精度大数乘法
void multiply() {int carry = 0;for (int i = 30; i > 0; i--) {result[i] = result[i] * ruleCountForCurrentDigit + carry;carry = result[i] / 10;result[i] %= 10;}
}int main() {result[30] = 1;// 输入传递进来的数和规则数scanf("%s %d", inputStr, &totalRules);int length = strlen(inputStr);// 将输入的数分装到数组 digits 中for (int i = 0; i < length; i++) {digits[i + 1] = inputStr[i] - '0';}// 输入规则for (int i = 1; i <= totalRules; i++) {int x, y;scanf("%d %d", &x, &y);rules[x][++ruleCounts[x]] = y;}// 处理每个数字for (int i = 1; i <= length; i++) {ruleCountForCurrentDigit = 1;// 对当前数字进行深度优先搜索for (int j = 1; j <= ruleCounts[digits[i]]; j++) {dfs(digits[i], rules[digits[i]][j]);}multiply();}int firstNonZeroIndex = 0;while (result[firstNonZeroIndex] == 0) {firstNonZeroIndex++;}// 输出结果for (int i = firstNonZeroIndex; i <= 30; i++) {printf("%lld", result[i]);}return 0;
}

以下是对这段 C 语言代码的解析：

一、整体功能概述

这段代码的目的是根据给定的一个整数和一组数字转换规则，计算经过任意次转换后可能得到的不同整数的数量，并以高精度大数的形式输出结果。

二、函数解析

1. dfs函数：

   • 这是一个深度优先搜索函数，用于确定一个数字的所有可能的转换规则数量。
   • 参数x和y分别代表当前数字和要转换到的数字。
   • 如果数字y已经被使用过，直接返回。
   • 将当前数字x标记为已使用，然后增加当前规则计数ruleCountForCurrentDigit。
   • 通过循环递归地处理数字y的转换规则，即对于数字y的每个可能的转换结果，再次调用dfs函数。
   • 最后将数字x标记为未使用状态。

2. multiply函数：

   • 这个函数用于处理高精度大数乘法。
   • 初始化进位变量carry为 0。
   • 从高位到低位遍历结果数组result，对于每一位，将其乘以当前规则计数ruleCountForCurrentDigit，再加上进位，得到新的值。然后更新进位为新值除以 10，当前位的值为新值对 10 取余。

三、主函数解析

1. 初始化部分：

   • 将结果数组result的最后一位初始化为 1，表示初始状态下有一种可能的结果。
   • 从标准输入读取一个字符串（表示输入的整数）和规则数量totalRules。
   • 计算输入字符串的长度，并将字符串中的数字逐个存入digits数组。
   • 初始化其他相关变量。

2. 输入规则部分：

   • 通过循环读取规则，将规则存入二维数组rules中，并记录每个数字对应的规则数量在ruleCounts数组中。

3. 处理每个数字部分：

   • 对于输入整数的每一位数字，将当前规则计数重置为 1。
   • 对于当前数字的每个转换规则，调用dfs函数进行深度优先搜索，以确定该数字的所有可能转换路径。
   • 调用multiply函数进行高精度乘法，更新结果数组。

4. 输出结果部分：

   • 找到结果数组中第一个非零的位置。
   • 从第一个非零位置开始输出结果数组中的数字。

四、时间复杂度和空间复杂度分析

1. 时间复杂度：

   • 读取输入和初始化的部分时间复杂度为$O(n)$，其中n是输入整数的长度和规则的数量。
   • dfs函数在最坏情况下，对于每个数字都可能进行多次递归调用，时间复杂度取决于规则的复杂程度和输入整数的大小，难以准确确定，但总体上与输入规模和规则数量相关。
   • multiply函数和输出结果的部分时间复杂度为$O(m)$，其中m是结果数组的长度。
   • 综合来看，时间复杂度较高，取决于输入规模和规则的复杂程度。

2. 空间复杂度：

   • 存储输入整数、规则和结果数组等变量占用一定的空间，空间复杂度为$O(n+k+m)$，其中n是输入整数的长度，k是规则的数量，m是结果数组的长度。

C++实现：

#include <iostream>
#include <string>// 全局变量定义
std::string inputNumber;
int digitArray[33];
int ruleCountForDigit[33];
int transformationRules[33][16];
int totalRuleCount;
int currentRuleCount;
bool usedDigits[10];
long long resultArray[33];// 深度优先搜索函数，判断一个数字的转化规则
void dfs(int x, int y) {// 如果 y 已经被使用过，直接返回if (usedDigits[y]) return;usedDigits[x] = true;currentRuleCount++;// 递归处理 y 的转化规则for (int i = 1; i <= ruleCountForDigit[y]; i++) {dfs(y, transformationRules[y][i]);}usedDigits[x] = false;
}// 处理高精度大数乘法
void multiply() {int carry = 0;for (int i = 30; i > 0; i--) {resultArray[i] = resultArray[i] * currentRuleCount + carry;carry = resultArray[i] / 10;resultArray[i] %= 10;}
}int main() {resultArray[30] = 1;// 输入传递进来的数和规则数std::cin >> inputNumber >> totalRuleCount;int length = inputNumber.length();// 将输入的数分装到数组 digitArray 中for (int i = 0; i < length; i++) {digitArray[i + 1] = inputNumber[i] - '0';}// 输入规则for (int i = 1; i <= totalRuleCount; i++) {int x, y;std::cin >> x >> y;transformationRules[x][++ruleCountForDigit[x]] = y;}// 处理每个数字for (int i = 1; i <= length; i++) {currentRuleCount = 1;// 对当前数字进行深度优先搜索for (int j = 1; j <= ruleCountForDigit[digitArray[i]]; j++) {dfs(digitArray[i], transformationRules[digitArray[i]][j]);}multiply();}int firstNonZeroIndex = 0;while (resultArray[firstNonZeroIndex] == 0) {firstNonZeroIndex++;}// 输出结果for (int i = firstNonZeroIndex; i <= 30; i++) {std::cout << resultArray[i];}return 0;
}

Java 实现：

import java.util.Scanner;class Main {static String inputNumber;static int[] digitArray = new int[33];static int[] ruleCountForDigit = new int[33];static int[][] transformationRules = new int[33][16];static int totalRuleCount;static int currentRuleCount;static boolean[] usedDigits = new boolean[10];static long[] resultArray = new long[33];// 深度优先搜索函数，判断一个数字的转化规则static void dfs(int x, int y) {// 如果 y 已经被使用过，直接返回if (usedDigits[y]) return;usedDigits[x] = true;currentRuleCount++;// 递归处理 y 的转化规则for (int i = 1; i <= ruleCountForDigit[y]; i++) {dfs(y, transformationRules[y][i]);}usedDigits[x] = false;}// 处理高精度大数乘法static void multiply() {long carry = 0;for (int i = 30; i > 0; i--) {resultArray[i] = resultArray[i] * currentRuleCount + carry;carry = resultArray[i] / 10;resultArray[i] %= 10;}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);inputNumber = scanner.next();totalRuleCount = scanner.nextInt();int length = inputNumber.length();// 将输入的数分装到数组 digitArray 中for (int i = 0; i < length; i++) {digitArray[i + 1] = inputNumber.charAt(i) - '0';}// 输入规则for (int i = 1; i <= totalRuleCount; i++) {int x = scanner.nextInt();int y = scanner.nextInt();transformationRules[x][++ruleCountForDigit[x]] = y;}resultArray[30] = 1;// 处理每个数字for (int i = 1; i <= length; i++) {currentRuleCount = 1;// 对当前数字进行深度优先搜索for (int j = 1; j <= ruleCountForDigit[digitArray[i]]; j++) {dfs(digitArray[i], transformationRules[digitArray[i]][j]);}multiply();}int firstNonZeroIndex = 0;while (resultArray[firstNonZeroIndex] == 0) {firstNonZeroIndex++;}// 输出结果for (int i = firstNonZeroIndex; i <= 30; i++) {System.out.print(resultArray[i]);}}
}

💐The End💐点点关注，收藏不迷路💐