算法标签：

bfs 模拟

题目分析

本题的代码实现了一个特定数字序列的生成和查询功能。该数字序列由一些不包含重复数字的整数构成，通过广度优先搜索（BFS）的方式，不断在已有的数字后面添加 0 - 9 中未出现过的数字来生成新的数字，最终根据用户输入的序号查询对应位置的数字。

代码思路

1. 结构体定义

定义了一个名为 Number 的结构体，其中包含两个成员变量：

• value：表示数字的实际值。
• digits：用二进制位来表示该数字中包含哪些数字位。例如，如果 digits 的第 i 位为 1，则表示数字 value 中包含数字 i。

2. 初始化

初始化 1 - 9 的数字，将它们存储在 num 数组中。对于每个数字 i，其 value 就是 i，digits 是 1 << i，表示该数字包含数字 i。

3. 广度优先搜索（BFS）生成数字序列

使用 BFS 的思想，从已有的数字开始，不断在后面添加 0 - 9 中未出现过的数字，生成新的数字。具体步骤如下：

• 初始化 n 为 10，表示已经有 1 - 9 这 9 个数字，k 为 1，表示从第一个数字开始处理。
• 当 n 小于 LIMIT 时，取出 num[k] 的 value 和 digits。
• 遍历 0 - 9 的数字 i，如果 digits 中不包含数字 i（即 !(d & 1 << i)），则生成一个新的数字 v * 10 + i，并更新其 digits 为 d | 1 << i，将新数字存储在 num[n] 中，并将 n 加 1。
• k 加 1，继续处理下一个数字。

4. 查询

通过 scanf 读取用户输入的序号 k，当 k 不为 0 时，输出 num[k].value，即序号为 k 的数字的实际值。

代码解释

#include <cstdio>
#define MAX 	1000010
#define LIMIT	1000001

// 定义 Number 结构体
struct Number{
	int value; // 数字的实际值
	int digits; // 用二进制位表示该数字中包含哪些数字位
	Number(){}
	Number(int v, int d) : value(v), digits(d){}
} num[MAX];

int main()
{
	// 初始化 1 - 9 的数字
	for(int i = 1; i < 10; ++i) num[i] = Number(i, 1 << i);
	// BFS 生成数字序列
	int n = 10, k = 1;
	for(; n < LIMIT; ++k){
		int v = num[k].value, d = num[k].digits;
		for(int i = 0; i < 10; ++i){
			if(!(d & 1 << i)) num[n++] = Number(v * 10 + i, d | 1 << i);
		}
	}
	// 查询
	while(scanf("%d", &k), k) printf("%d\n", num[k].value);
	return 0;
}

复杂度分析

• 时间复杂度：生成数字序列的时间复杂度为 $O(N)$，其中 $N$ 是生成的数字序列的长度。查询的时间复杂度为 $O(1)$。
• 空间复杂度：主要用于存储数字序列，空间复杂度为 $O(N)$。

注意事项

• 代码中使用了 #define 来定义常量，确保在代码中使用这些常量时不会出现拼写错误。
• 代码中使用了二进制位运算来判断数字中是否包含某个数字位，这种方法可以提高代码的效率。