解题思路

代码解析

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6 + 10;

char ans[N];  // 存储最终序列的字符数组
int node[N];   // 记录每个节点的当前可用边（数字0-9的访问情况）
int sta[N];    // 栈，用于存储DFS过程中的边
int n, m;      // n为输入参数，m为节点总数（10^(n-1)）
int cnt;       // ans数组的计数器
int sum;       // sta栈的计数器

void solve(int v) {
    int w;
    while (node[v] < 10) { // 遍历当前节点的所有可能边（数字0-9）
        w = 10 * v + node[v]; // 构造边对应的n位序列（v为前n-1位，node[v]为最后一位）
        node[v]++; // 移动到下一个数字
        sta[sum++] = w; // 将边对应的n位序列压入栈
        v = w % m; // 转移到下一个节点（取后n-1位作为新节点）
    }
}

int main() {
    while (~scanf("%d", &n) && n) { // 循环处理每个测试用例
        int w = 0;
        m = 1;
        cnt = 0;
        sum = 0;
        if (n == 1) { // 特殊处理n=1的情况（所有1位数字序列为0-9）
            cout << "0123456789\n";
            continue;
        }
        for (int i = 0; i < n - 1; i++) { // 计算节点数m=10^(n-1)
            m *= 10;
        }
        for (int i = 0; i < m; i++) { // 初始化每个节点的可用边为0（未访问数字0）
            node[i] = 0;
        }
        solve(0); // 从节点0开始DFS遍历
        while (sum) { // 处理栈中的边，生成序列
            w = sta[--sum]; // 取出边对应的n位序列
            ans[cnt++] = w % 10 + '0'; // 记录最后一位数字
            solve(w / 10); // 回溯到前一个节点，继续处理剩余边
        }
        // 输出前n-1位的前导零（构造序列的初始状态）
        for (int i = 1; i < n; i++) {
            cout << "0";
        }
        // 逆序输出ans数组，得到正确的序列顺序
        while (cnt) {
            cout << ans[--cnt];
        }
        cout << endl;
    }
    return 0;
}

关键点说明

1. DFS遍历：

   • solve(v) 函数通过递归（隐式使用栈）遍历节点 v 的所有出边，确保每条边（即每个 ( n ) 位序列）被访问一次。
   • node[v] 记录当前节点 v 已访问的数字数量，避免重复访问同一条边。

2. 序列生成：

   • 栈 sta 存储遍历过程中的边（即 ( n ) 位序列），处理时从栈顶取出边，记录其最后一位数字。
   • 由于DFS是逆序处理边，最终需要逆序输出结果，以确保序列顺序正确。

3. 前导零处理：

   • 初始状态为全零的 ( n-1 ) 位节点，因此在序列开头需要补充 ( n-1 ) 个零，确保第一个 ( n ) 位序列正确生成。

总结

该算法利用德布鲁因序列的性质，通过DFS遍历有向图的欧拉回路，高效构造出包含所有 ( n ) 位数字序列的最短序列。时间复杂度为 ( O(10^n) )，适用于 ( n \leq 6 ) 的范围（( 10^6 ) 规模可接受）。通过栈模拟递归过程，避免了显式递归的栈溢出问题，确保了代码的稳定性和效率。