注意到最多有$2^k$个01串, 构造是不太可能的
代码不难, 转换图的思想却很难想到(不放专题里, 我是想不到转换图做)
注意到任何一个串可以通向两个另外的串, 也由两个串可以到达, 故每个串的入度和出度都为2
注意到这$2^k$串组成的图是个欧拉图, 那么必定存在欧拉回路, 之后就是怎么走路径最小了
当然是走边的时候选择先走 +0 的边了
int n, m, _, k, a, ans[2050];
bool v[2050];
bool dfs(int x, int k) {
if (k == (1 << n)) return 1; v[x] = 1;
if (!v [(x << 1) & a]) if (dfs((x << 1) & a, k + 1)) return ans[k] = 0, 1;
if (!v[(x << 1 | 1) & a]) if (dfs((x << 1 | 1) & a, k + 1)) return ans[k] = 1;
return v[x] = 0;
}
int main() {
cin >> n; a = 1 << n;
cout << a-- << ' '; dfs(0, 1);
for (int i = 1; i <= n; ++i) cout << 0;
for (int i = 1; i <= a - n + 1; ++i) cout << ans[i];
return 0;
}