BZOJ

分析

先考虑 $m$ 最大能取到多少,显然是 $2^k$ ,此时所有 01 串都出现了一次。

考虑怎么构造出 $2^k$ 。

把所有 $0\sim m-1$ 的数看作点,如果 $i$ 能够通过丢掉最高位再在后面补一个 0/1 得到 $j$ ,就从 $i$ 向 $j$ 连一条边权为 0/1 的边。

那么只要找一条字典序最小的欧拉回路就好了,直接 dfs 即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1<<11;

int k,m,lim;
int vis[N],ans[N];

inline int dfs(int u,int p) {
    if (vis[u]) return 0;
    vis[u]=1,ans[p]=u&1;
    if (p==m) return 1;
    if (dfs((u<<1)&lim,p+1)) return 1;
    if (dfs((u<<1)&lim|1,p+1)) return 1;
    vis[u]=0,ans[p]=0;
    return 0;
}

int main() {
    k=read(),m=1<<k,lim=m-1;
    dfs(lim-1,1);
    printf("%d\n",m);
    for (re int i=1;i<=m;++i) putchar("01"[ans[i]]);
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 34 PM