## $hihoCoder$ $1182$ 欧拉路·三 > **注**：因$HihoCoder$已关闭，无法访问，只好从网上找到原题的图片和文字，本题无法上$OJ$进行校验。 > ### 一、题目描述 ![](https://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/%7Byear%7D/%7Bmonth%7D/%7Bmd5%7D.%7BextName%7D/20230807100545.png) ![](https://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/%7Byear%7D/%7Bmonth%7D/%7Bmd5%7D.%7BextName%7D/20230807100809.png) **题目抽象** 写出一个环，环上有$2^n$个格子，每个格子中的数字是$0$或$1$，相连着的$n$个格子可以组成一个数的二进制，要求给出这$2^n$个数字的序列，使得组成的$2^n$个数字全是不同的。(即从$0$到$2^n-1$） ### 二、解题思路 **兹鼓欧拉回路** 问题。 构造一个图，但是只需要考虑边，每条边假设为$n$个$0/1$组成的串，即此图有$2^n$条边，每边代表$1$个数字。 若两边经过同一个点，则可以从一条边$k$经过 $(k<<1)+0/1$就是左边去掉$1$位，再左移一位，再在后面添加$0$或$1$，就相当于切换到另外一边。 既然可以在后面添加$0$或$1$，那么就相当于一个点有两条出边，那么也就可以看到每个点也有两条入边。边$1001$和$0001$都可以转成$0011$和$0010$。此时他们经过了$1$个点，前两条边为入边，后两条边为出边（如图）。 ![](https://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/%7Byear%7D/%7Bmonth%7D/%7Bmd5%7D.%7BextName%7D/20230807143506.png) **栗子** > $n = 3$; 则建$2^{n-1}$个点，也就是$4$个点，分别是 $00，01，11，10$; 这四个点共可以连出$8(2^3 -> 2^n)$条边出来。 这样就转化位求欧拉路径的题了。求一条路径不重复地经过这$8$条边； **细节** 可以从$0$开始出发，进行$dfs$，需要注意的只是路径应该是欧拉路的路径，要从回溯开始计起，为了防止无限循环，要记录下访问过的路径。但是所要的答案是顺时针的，所以要从路径的前面开始输出。每次输出二进制的首位即可。 我们每次从扩展$0$或$1$的边, 为了防止越界, 在%一下$len$. 然后根据建边的不同构造出来的可行路是不同的. 后面有道题是要输出字典序最小的路, 所以在那个题需要注意下建边顺序.而这道题不要求什么顺序, 所以随便输出一个可行路就可以了。 ### $Code$ ```cpp {.line-numbers} #include using namespace std; /* 举栗子：以下面的小方框个数=3为例，其实是模拟了4个点，8条边，也就是(00,01,10,11)->通过尾部加0或加1->构建边->(000,001,010,011,100,101,110,111)-> 去掉头部第1个->(00,01,10,11) 其中 4=2^2=2(3-1),8=2^3,推广一下，如果下面的小方框个数是n,点数2^(n-1),边是2^n=[0000...0,1111...1]条 题目中要求1<=N<=15,那么我们加大一点范围，就让N=16,但是，由于此时N的含义是边的个数，也就是M=N*2，下面的代码，含糊了N和M的概念，将其都设定为1<<16,这样足够大，并且不超过题目要求 */ const int N = 1 << 16, M = N; int len; int res[N], rl; // 路径记录器 int st[N]; // 某条边是不是出现过了 // 链式前向星 int e[M], h[N], idx, w[M], ne[M]; void add(int a, int b, int c = 0) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++; } // dfs求有向图欧拉回路 void dfs(int u) { for (int i = h[u]; ~i; i = ne[i]) { int v = e[i]; // u通过i号索引这条边，走向了v点。 int id = w[i]; if (st[id]) continue; // 如果i这条边访问过了，那么不需要重复访问 st[id] = 1; // 标记i号边已访问过 dfs(v); // 递归搜索v号点 // cout << "u=" << u << ",v=" << v << "," // << "w[i]=" << w[i] << endl; res[++rl] = w[i]; // 以边的形式记录欧拉路径,i号索引的这条边，它的真实边号为w[i] } } int main() { #ifndef ONLINE_JUDGE freopen("HihoCoder1182.in", "r", stdin); #endif int n; scanf("%d", &n); memset(h, -1, sizeof h); /* len的第一层含义 一、现在点是10（二进制表示），对应十进制是就是2号点，现在需要它扩展出边来，当然就是100,101 二、那么，这两条边走向了哪两个节点呢？ (1)10->加0->生成边-> 100 ->哪个节点? (2)10->加1->生成边-> 101 ->哪个节点? 其实用人眼看是走到了00和01两个点，也就是去掉最前面的那个数字1就行。 那如何让计算机知道它们走向了哪两个点呢？办法就是取模！就是将边对应的数字对4取模，则最前面的二进制1将被裁掉，只保留最后两位的00和01 那么，这个4是怎么来的呢？其实就是 1<< (n-1)! 总结：我们只要对生成的边对应的十进制数字，对 len= 1<<(n-1) 取模，就可以获得到它走向了哪个点ID */ len = 1 << (n - 1); // len的第二层含义：如果点号从0开始计数，那么，最大的点号也是 1<<(n-1),以n=3为例，四个点就是(0,1,2,3),最大点号 3= (1<<(3-1)) -1 for (int a = 0; a < len; a++) { int num = a << 1 | 1; // 点号，左移一位，尾部添1，以10为例，就是变成 100+1=101，这是一个点到边的变换过程,num是指边号对应的十进制数，比如101=5 int b = num % len; // 再模一下我们精心准备的len,就可以把头部第1位裁掉，得到目标节点号 add(a, b, num); // 从a点出发，到b点去，通过一条边号为num的边.我们把链式前向星魔改了一下，把边权重定义为边的边号 num = a << 1; // 点号，左移一位，尾部添0，以10为例，就是变成 100，这是一个点到边的变换过程,num是指边号对应的十进制数，比如100=4 b = num % len; // 再模一下我们精心准备的len,就可以把头部第1位裁掉，得到目标节点号 add(a, b, num); // 从a点出发，到b点去，通过一条边号为num的边.我们把链式前向星魔改了一下，把边权重定义为边的边号 // 上面这段，配置题解中的图进行理解效果更佳！ } /* Q:兹鼓欧拉回路,为啥题意这样的东西能和欧拉回路搞在一起，它们之间有什么联系？ 答：根据题解中的图，和上面我们的建边，我们可以理解：所有的点都有两条出边，也都有两条入边！也就是它的出度=2，入度=2 图是连通的（二进制的性质保证了没有孤立点）,并且,每个点的出度入度都是偶数，都等于2，这恰好是欧拉回路的充要条件！这才是这两个好基友合并的基础！ 既然已经确定题目的类型是欧拉回路，那只要我们求出任意一条欧拉回路就可以了，因为0号点是肯定存在的，（当然，你也可以从任何存在的点号出发，本题说任意一条合理的路径就行）,我们 从0号点开始搜索，从深搜的dfs(v)后，在循环内记录边即可。 注意：如果不是记录边，而是记录点的话，需要在深搜dfs(v)后，在循环外记录点才可以，这是差别！ */ dfs(0); /* 题目要求：输出 1个长度为2^n的01串，表示一种符合要求的分布方案 理解：将这个串把顺序一个一个进入下面的小方框，就可以获取到所有的数字组合。 那与我们已经记录下来的边有什么关系呢？ 以本题的样例答案00010111为例进行解释：(下面的小方框是3个) （1）倒数第1位1下来进入小方框，得到001 （2）倒数第2位1下来进入小方框，得到011 （3）倒数第3位1下来进入小方框，得到111 （4）倒数第4位0下面进入小方框，将最前面的1弹出，得到110 （5）倒数第5位1下面进入小方框，将最前面的1弹出，得到101 （6）倒数第6位0下面进入小方框，将最前面的1弹出，得到010 （7）倒数第7位0下面进入小方框，将最前面的0弹出，得到100 （8）倒数第8位0下面进入小方框，将最前面的0弹出，得到000 将dfs函数中我注释掉的代码放开，可以得到如下的代码运行结果 u=2,v=0,w[i]=4 =(100) u=3,v=2,w[i]=6 =(110) u=3,v=3,w[i]=7 =(111) u=1,v=3,w[i]=3 =(011) u=2,v=1,w[i]=5 =(101) u=1,v=2,w[i]=2 =(010) u=0,v=1,w[i]=1 =(001) u=0,v=0,w[i]=0 =(000) 参考答案：00010111 此时，你会惊奇的发现，只要把得到的结果倒序，并且每次截取最前面一位的数字，拼装起来就是参考答案! Q：为什么会有这么神奇的现象呢？ 答：因为是队首出列啊，所以，对于每个路径，当然是只取最前面的那一位了！ 也就是把序列倒序来看， 000->被顶出去->0 001->被顶出去->0 010->被顶出去->0 101->被顶出去->1 011->被顶出去->0 111->被顶出去->1 110->被顶出去->1 100->被顶出去->1 Q:怎么样能截取最前面的第一位呢？就不再是取模了，而用除法啦！ res[i]/len就是答案！其中len=4,也就是去掉最后两位的意思！ */ for (int i = rl; i; i--) printf("%d", res[i] / len); return 0; } ``` ### 邻接矩阵实现 ```cpp {.line-numbers} #include #include #include #include #include using namespace std; const int N = 400010; int n; int g[N][2]; vector res; // 欧拉回路 void dfs(int u) { for (int i = 0; i < 2; i++) { int v = g[u][i]; if (~g[u][i]) { g[u][i] = -1; dfs(v); } } res.push_back((u & 1)); // 保存最后一位 } int main() { #ifndef ONLINE_JUDGE freopen("HihoCoder1182.in", "r", stdin); #endif memset(g, -1, sizeof g); int u; // 小方框数量 scanf("%d", &u); n = (1 << (u - 1)); // 点的数量 for (int i = 0; i < n; i++) { // 每个顶点，都有两条出边 int t = ((i << 1) & (n - 1)); // 建图,干掉首位 g[i][0] = t; // 每个点最多能连两条边，0或1 g[i][1] = t + 1; } dfs(0); for (int i = res.size() - 1; i; i--) // 倒序输出，最后一位顶点起点重合 printf("%d", res[i]); return 0; } ```