题解：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

个即可。

实现（仅供参考）

CPP

1234567891011121314151617181920212223242526272829303132333435363738394041#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;
}

题解：UVA10040 Ouroboros Snake

文章操作

相关推荐

评论

题解：UVA10040 Ouroboros Snake