大转盘

大转盘

时间限制：1 sec

空间限制：256 MB

问题描述

邓老师有一个大转盘，被平分成了 2^n 份。

邓老师还有一个长度为 2^n 的数组 a（下标从 0 开始），其中的每个元素都是 0 或

1。于是邓老师就可以选择大转盘上的一个位置，将 a[0] 填入其中，然后按顺时针顺序依次将 a[1],a[2],…,a[2^n-1] 填入。

对于大转盘上的一个指定位置，邓老师可以从它开始，取出顺时针方向的 n 个位置，并将它们按原顺序拼接起来，得到一个长度为 n 的 01 串，也就是一个 n 位二进制数。我们把这个二进制数称作从这个位置开始的幸运数。

显然地，大转盘上共有 2^n 个位置可以获得幸运数，而巧合的是 n 位二进制数恰好也有

2^n 个，所以邓老师希望这些所有的幸运数包含了所有的 n 位二进制数。请输出一个数组 a，使其满足邓老师的要求。（如果有多解，输出任一即可） 下面是一个 n=3 的例子（即样例）。

输入格式

一行一个整数 n。

输格式

输出一行 2^n 个字符，第 i 个字符（1<=i<=2^n）表示 a[i-1]。

样例输入

样例输

数据范围

本题包含 16 个测试点。对于第 i 个测试点（1<=i<=16），满足 n=i。

提示

[如果把所有 n-1 位二进制数建立节点，将所有的 n 位二进制数视为单向边。对于边 x， 设其前 n-1 位为 u，后 n-1 位为 v，则其连接 u,v。]

[在这张图上求出欧拉回路，想一想，答案与欧拉回路有何关联呢？]

代码

//#include <bits/stdc++.h> #include <vector>

#include <iostream> #include <sstream>

#pragma warning(disable:4996) using namespace std;

// ================= 代码实现开始 =================

/* 请在这里定义你需要的全局变量 */

int allOne; vector<bool> vis[2]; string ans;

int twoPow(int x)

{

return 1 << x;

}

void dfs(int u)

{

for (int i = 0; i < 2; ++i)

{

if (!vis[i][u]) {

int v = ((u << 1) | i) & allOne;

vis[i][u] = 1;

dfs(v);

ans.push_back('0' + i);

}

}

}

// 本函数求解大转盘上的数，你需要把大转盘上的数按顺时针顺序返回

// n：对应转盘大小，意义与题目描述一致，具体见题目描述。

// 返回值：将大转盘上的数按顺时针顺序放到一个string中并返回string getAnswer(int n) {

/* 请在这里设计你的算法 */

allOne = twoPow(n - 1) - 1;

ans = "";

for (int i = 0; i < 2; ++i)

vis[i].resize(twoPow(n - 1), 0);

dfs(0);

return ans;

}

// ================= 代码实现结束 =================

int main() {

int n;

scanf("%d", &n);

cout << getAnswer(n) << endl;

return 0;

}