无向图的欧拉回路：
1.图连通；
2.图所有点度数均为偶数；
//欧拉路径要求起点和终点度数为奇数；
有向图的欧拉回路：
1.图连通；
2.图所有点入度等于出度；
//欧拉路径要求起点入度=出度-1，终点入度=出度+1；
欧拉回路：通过图中每条边一次且仅一次，并且过每一顶点的回路。
关键词是：每条边仅经过一次。
也就是说如果一道题建图后，要求一条回路（路径），每条边经过且仅经过一次。
回到这道题：
显然长度为2^k。
网上看到的题解只有这个讲的是正确的。
https://blog.csdn.net/SSL_Yyx/article/details/81037593?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.nonecase
即：把2^k个数当成边，设出2^(k-1)个点。
然后再跑欧拉回路。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define ls (o<<1) #define rs (o<<1|1) #define pb push_back const double PI= acos(-1.0); const int M = 1e5+7; int sk[M],sp[M],vs[M],nm[M]; int ans[M]; int main() { ios::sync_with_stdio(false); cin.tie(0); int k; cin>>k; //以k=3为例 int n=1<<(k-1);//4个点：00 01 10 11 int m=1<<k;//8条边：000 001 010 100 110 011 101 111 int tp=(1<<(k-1))-1; int t=0,top=0; sk[++top]=0; while(top) { int x=sk[top]; int v=(x<<1)&tp;// abc -> bc0 int w=x<<1; if(vs[w]) { v++;w++; if(vs[w]) { ans[++t]=sp[top]; top--; } else sk[++top]=v,sp[top]=1,vs[w]=1; } else sk[++top]=v,sp[top]=0,vs[w]=1; } cout<<m<<" "; for(int i=1;i<k;i++)cout<<0; for(int i=t-1;i>=k;i--)cout<<ans[i]; cout<<endl; return 0; }
