CF325E Red Button Solution
yyyyxh
·
·
题解
感觉题解区的叙述偏繁琐……提供一个相对简单点的做法？
首先可以发现奇数无解。
发现找哈密顿回路是难的，但我们发现这道题每个点出度和入度都为二，提示我们用欧拉回路。
然而这种欧拉回路不能直接构造出解。我们考虑这道题的特殊连边方式：
对于 i<\frac{n}{2} 的点向 2i,2i+1 连边。
发现 $i$ 与 $i+\frac{n}{2}$ 连边情况相同。那么我们只保留第一类边，边上标上这条边指向的节点的编号，这些边形成了一颗满二叉树。然后让满二叉树的叶子节点 $i$ 向 $i-\frac{n}{2}$ 连一条虚边，边上不标数。
这依然满足出入度平衡且原图弱联通。跑一遍欧拉回路把边上标的数字串起来就是答案了。
```cpp
#include <cstdio>
using namespace std;
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
const int N=100003;
int hd[N],cur[N],ver[N<<1],nxt[N<<1],tot;
void add(int u,int v){
nxt[++tot]=hd[u];hd[u]=tot;ver[tot]=v;
}
int stk[N<<1],tp;
void dfs(int u){
for(int i=cur[u];i;i=cur[u]){
cur[u]=nxt[i];dfs(ver[i]);
}
stk[++tp]=u;
}
int main(){
int n=read();
if(n&1){puts("-1");return 0;}
for(int i=0;i<(n>>1);++i){
add(i,i<<1);add(i,i<<1|1);add(i+(n>>1),i);
}
for(int i=0;i<n;++i) cur[i]=hd[i];
dfs(0);
int las=-1;
while(tp){
if(stk[tp]>las) printf("%d ",stk[tp]);
las=stk[tp--];
}
putchar('0');
putchar('\n');
return 0;
}
```