Gray Code (格雷码)

题目：

思路：

这里有两个思路，如果我们不了解 gray code 这个东西那么我们如何去想？

由于这里数据小，其实我们可以使用图论的方式来写，当然也可以找规律构造，其实这属于方法二

图论：

我们给每个数都写出其二进制形式，然后探究其下一个 gray code 是谁，那么我们就可以根据其性质分析，由于我们只需要一位不同，那么直接异或每一位就能求出其下一个节点的可能，由于 n <= 16，那么我们一个节点最多只有 16 个节点，所以我们直接建图然后跑一遍即可，由于一定有解，所以直接模拟即可，1 << 16 约为 7e4，可过

构造：

根据性质，我们对于位置 i，我们对应的 gray code 就是 i ^ (i >> 1)，具体证明不在本次讨论范围内

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int n, mx;
string num[70000];
vector<vector<int>> g(70000);
string to2(int x)
{string ans;for (int i = n - 1; i >= 0; i--){ans += '0' + ((x >> i) & 1);}return ans;
}
int sonans[70000];
int vis[70000];
int over = 0;
void dfs(int fa, int len)
{if (over || len == mx+1){over = 1;return;}vis[fa] = 1;for (auto & son : g[fa]){if(vis[son] || over) continue;sonans[fa] = son;dfs(son,len + 1);}vis[fa] = 0;
}int graycode[70000];
void solve2()
{cin >> n;for (int i = 0; i < 1<<n; i++){graycode[i] = i ^ (i >> 1);cout << to2(graycode[i]) << endl;}  
}void solve()
{cin >> n;mx = pow(2, n) - 1;for (int i = 0; i <= mx; i++){num[i] = to2(i);for (int j = n - 1; j >= 0; j--){g[i].push_back(i ^ (1LL << j));}}dfs(0,1);int now = 0;while (now != -1){cout << num[now] << endl;now = sonans[now];}
}signed main()
{memset(sonans,-1,sizeof sonans);ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;while (t--){solve2();}return 0;
}