C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 496K, 提交时间: 2020-10-05 19:13:13

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 2505;
int ans[maxn];
int k,n;
int vis[maxn];
int dfs(int cur,int len){
	if(len==n){
		//ans[len] = cur&1;
		return 1;
	}
	if(vis[cur])return 0;
	vis[cur] = 1;
	ans[len] = cur&1;
	if(dfs((cur<<1)&(n-1),len+1))return 1;
	if(dfs(((cur<<1)|1)&(n-1),len+1))return 1;
	vis[cur]=0;
	return 0;
}
int main(){
	cin>>k;
	n = (1<<k);
	cout<<n<<" ";
	dfs(0,0);
	for(int i=0;i<k-1;i++)cout<<0;
	for(int i=0;i<n-(k-1);i++){
		cout<<ans[i];
	}
} 

C++(clang++11) 解法, 执行用时: 8ms, 内存消耗: 380K, 提交时间: 2020-11-20 22:24:06

#include<bits/stdc++.h>
using namespace std;

int vis[50000];
int ans[50000];
int n,m; 

void dfs(int x,int y)
{
//	cout<<x<<" "<<y<<endl; 
	if (vis[x]==1) return;
	vis[x]=1;
	if (y>n) return;
	ans[y]=x&1;
	int g;
	if (x==0) g=0;
	else g=x%m;
	dfs(g<<1,y+1);
	dfs(g<<1|1,y+1);
}

int main()
{
	int k;
	cin>>k;
	n=1<<k;
	m=1<<(k-1);
	cout<<n<<" ";
//	vis[0]=1;
	dfs(0,k);
	for (int i=1;i<=n;i++) cout<<ans[i];
	cout<<endl;
	return 0;
}