这个题，正赛的时候也没有过，不过其实已经有了正确的解法，可惜时间不多了，就没有去尝试。
题意是有n个点，i点能通向i-1，然后i和i*2、i*2+1互通。
请你构造一种路径从1能走完所有点，并且不重复经过每个点。
一开始我先考虑了有什么方法能固定地走完所有点。
然后发现 1-(2)-(4)-3-(6)-5-(10)....()为跳跃
仅当走完了之前的所有点时才跳跃，跳跃完后再回退走完所有点。
这样走的话，是可以走完所有点的。
但是这样的限制是，我们只能在n=1/2/4/6/10...这些数时走完所有点，这个可行的集合可以用ai=(a(i-2)+1)*2来递推。
换句话说，我们只要求出数列a 就可以按这个数列走出方案。
这个题目i可以通向i*2，也可以通向i*2+1，所以我们得到了另一种移动方式ai=(a(i-2)+1)*2+1。
这样我们能走的数就多了许多（其实是全部数都能走完 233）
我们只要从ai=n 反向推这个数列前面的项，显然a(i-2)=ai/2-1或者(ai-1)/2-1
而且这个其实是固定的，奇数的话想/2一定要-1,偶数反之。
然后我们就求出了这个数列的ap ap-2 ap-4.....
数列的其他项其实不重要 只要满足ap>ap-1即可，可以随便构造(大概)。
以下为具体代码
#include<bits/stdc++.h> using namespace std; int i,i0,n,m,T; bool vis[100005]; stack<int>stk; vector<int>v; int main() { vis[0]=1; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i=1;i<=n;i++)vis[i]=0; v.clear(); while(1) { if(n<=1)break; stk.push(n); if(n%2)n=(n-1)/2-1; else n=n/2-1; } int now=1; while(1) { v.push_back(now); vis[now]=1; if(!vis[now-1])now--; else { if(stk.empty())break; else if(now*2==stk.top()) { now*=2; stk.pop(); } else if(now*2+1==stk.top()) { now=now*2+1; stk.pop(); } else { if(!vis[now*2])now=now*2; else now=now*2+1; } } } for(i=0;i<v.size();i++)printf("%d%c",v[i],i==v.size()-1?' ':' '); } return 0; }