python/TangDou/AcWing/EulerPath/400.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 1 << 12;
const int M = 4 * N;

int n, m, t;

// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

vector<int> stk;
void dfs(int u) {
    while (~h[u]) {
        int y = e[h[u]];
        h[u] = ne[h[u]];
        dfs(y);
    }
    stk.push_back(u);
}

int main() {
    memset(h, -1, sizeof h); // 初始化链式前向星
    scanf("%d", &n);         // n个传感器

    int t = (1 << (n - 1)) - 1;
    for (int i = 0; i < (1 << (n - 1)); i++) {
        add(i, ((i << 1) & t) | 1);
        add(i, (i << 1) & t);
    }

    dfs(0);
    printf("%d ", 1 << n);

    while (stk.size() > 1) putchar((stk.back() >> (n - 2)) + '0'), stk.pop_back();
    puts("");
    return 0;
}