python/TangDou/AcWing/EulerPath/POJ1392.md

POJ 1392-Ouroboros Snake

前置题目 hihoCoder 1182 欧拉路·三

【兹鼓欧拉回路】

这道题和上面那道题几乎一样, 算是变形题吧, 这道题要求构造的01字符串就是必须是字典序最小的, 在上面那道题的注意下建边的顺序即可. 因为是链式前向星法, 应该大边在前。

Code

#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <cstring>
#include <vector>
#include <stack>
#include <cstdio>

using namespace std;
const int N = 1 << 16, M = N;
int len;
int rl, res[N];
int st[N];

// 链式前向星
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++;
}

void dfs(int u) {
    for (int i = h[u]; ~i; i = h[u]) {
        int id = w[i];
        if (st[id]) continue;
        st[id] = 1;
        h[u] = ne[i]; // 删边的套路优化
        dfs(e[i]);
        res[rl++] = id;
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("POJ1392.in", "r", stdin);
#endif
    int n, k;
    while (scanf("%d%d", &n, &k), n + k) {
        idx = rl = 0;
        memset(h, -1, sizeof h);
        memset(st, 0, sizeof st);
        memset(res, 0, sizeof res);

        len = 1 << (n - 1);
        for (int a = 0; a < len; a++) {
            int c = a << 1 | 1;
            int b = c % len;
            add(a, b, c);

            c = a << 1;
            b = c % len;
            add(a, b, c);
        }
        dfs(0);
        // 输出这个序列生成的第K个数字是多少？
        printf("%d\n", res[rl - 1 - k]);
    }
    return 0;
}