题解：UVA10040 Ouroboros Snake

· · 题解

环形问题很容易想到回路。

考虑建立图论模型（技巧点 1），我们将 [0,2^n-1] 中的所有数作为节点，然后向他们能够转移到的节点连边，边权是 0/1，分别代表向末尾添加 0/1。设当前节点为 x，则它连向的节点编号为 (x<<1+w)&cover，其中 w 为边权，cover 为掩码，即 1<<(n-1)-1，用于提取末尾的 n-1 位。（技巧点 2）

这样建好图之后，跑出字典序最小的欧拉回路，在过程中倒序记录所有的 \operatorname{o}(n,k)（为什么是倒序请参考欧拉回路的实现），然后输出对应的倒数第 k 个即可。

:::success[实现（仅供参考）]

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define int long long
using namespace std;

const int N=(1<<25)+5;
int n,k;
int cnt[N];
vector<int> ans;

void dfs(int cur,int cover){
    while(cnt[cur]<2){
        int x=(cur<<1)+cnt[cur];
        cnt[cur]++;
        dfs(x&cover,cover);
        ans.push_back(x);
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(cin>>n>>k&&(n+k)){
        memset(cnt,0,sizeof cnt);
        ans.clear();
        int cover=(1<<(n-1))-1;
        dfs(0,cover);
        cout<<ans[ans.size()-1-k]<<'\n';
    }
    return 0;
}

:::