python/TangDou/AcWing/EulerPath/HihoCoder1182_2.cpp

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N = 400010;
int n;
int g[N][2];
vector<int> res;

// 欧拉回路
void dfs(int u) {
    for (int i = 0; i < 2; i++) {
        int v = g[u][i];
        if (~g[u][i]) {
            g[u][i] = -1;
            dfs(v);
        }
    }
    res.push_back((u & 1)); // 保存最后一位
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("HihoCoder1182.in", "r", stdin);
#endif
    memset(g, -1, sizeof g);
    int u; // 小方框数量
    scanf("%d", &u);
    n = (1 << (u - 1));               // 点的数量
    for (int i = 0; i < n; i++) {     // 每个顶点，都有两条出边
        int t = ((i << 1) & (n - 1)); // 建图,干掉首位
        g[i][0] = t;                  // 每个点最多能连两条边，0或1
        g[i][1] = t + 1;
    }
    dfs(0);

    for (int i = res.size() - 1; i; i--) // 倒序输出，最后一位顶点起点重合
        printf("%d", res[i]);
    return 0;
}