题意

其实就是求字典序最小的长度为2^k的01串使得子串不重复出现。

思路

第一个答案很直观可以得到2^k，然后第二个答案爆搜就行了。优先选择0，如果前面以及出现过相应子串就回退填1. 这是一道欧拉回路的题，如何理解呢？就是每个状态都可以连0或者1，都有两个入边和出边。那么必然存在一条路径可以使得走过所有点并且回到原状态，于是就可以求一个欧拉回路来实现这道题。

代码

#include<bits/stdc++.h>
const int N=1e4;
 
using namespace std;
int n,bin,vis[N],ans[N];
bool dfs(int val,int step){
    if(vis[val]) return 0;
    if(step==bin)return 1;
    vis[val]=1;
    int nxt1=(val<<1)&(bin-1),nxt2=(val<<1|1)&(bin-1);
    ans[step]=val&1;
    if(dfs(nxt1,step+1)||dfs(nxt2,step+1)) return 1;
    vis[val]=0;
    return 0;
}
signed main(){
    scanf("%d",&n);
	bin=1<<n;
    printf("%d ",bin);
    dfs(0,1);
    for(int i=1;i<n;i++) putchar('0');
    for(int i=1;i<=bin-n+1;i++) printf("%d",ans[i]);
    return 0;
}