\(POJ\) \(1392\)-\(Ouroboros\) \(Snake\)
// 这道题和上面那道题几乎一样, 算是变形题把, 这道题要求构造的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 = ne[i]) {
int v = e[i];
if (st[i]) continue;
st[i] = 1;
dfs(v);
res[rl++] = w[i];
}
}
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 num = a << 1 | 1;
int b = num % len;
add(a, b, num);
num = a << 1;
b = num % len;
add(a, b, num);
}
dfs(0);
// 输出这个序列生成的第K个数字是多少？
printf("%d\n", res[rl - 1 - k]);
}
return 0;
}