题目链接：http://acm.uestc.edu.cn/#/problem/show/1642

欧拉回路
考虑用一条边表示一个数，那么题目要求就是无重复的遍历完所有边，
则这是一个欧拉图的问题。

建图：

对于有公共点的两条边，第一个的后n-1位和第二个的前n-1相同。

这样将一条边的前n-1位和后n-1位作为点，连边，这样来表示它。
如：对于01101，我们可以从0110向1101建一条有向边表示01101.
于是所建图有2^(n-1)个点，和2^n条边。

对于任一两个点，如果它们的前n-2位和后n-2位相同，就连一条有向边，
这样所得到的图一定是欧拉图，因为每个点的入度和出度都是2，一定存在
欧拉回路。

#include <bits/stdc++.h>
using namespace std;
const int maxn = (1<<15)+7;
//2^(n-1)个点,2^n条边
vector <pair<int, int> > G[maxn];
bool vis[maxn];
vector <int> way;
int n;
void dfs(int u)
{
    int v, e;
    if(!G[u].empty()){
        v = G[u].back().second, e = G[u].back().first;
        G[u].pop_back();
        if(!vis[e]){
            vis[e] = 1;
            dfs(v);
            way.push_back(e);
        }
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < (1<<n); i++){
        int u = i>>1;
        int v = i % (1<<(n-1));
        G[u].push_back(make_pair(i,v));
    }
    memset(vis,0,sizeof(vis));
    dfs(0);
    way.clear();
    for(int i=0; i<(1<<n); i++){
        putchar(char('0'+(way[i]&1)));
    }
    putchar('\n');
    return 0;
}