题意
其实就是求字典序最小的长度为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;
}