题解：P7128 「RdOI R1」序列(sequence)
_WHX985_
·
·
题解
思路
题目标签也没有给任何的提示，但只要你读题仔细就能发现 2x 和 2x+1 仿佛在那里见过，你没有想错，在一棵二叉树上，一个节点编号为 x 的节点的左孩子编号为 2x 右孩子编号为 2x+1，当然这是在有的情况下。如果不理解大家就来看个图。圆圈中写的是节点的编号。
这样的话，思路就有了。建立一个 vis 数组记录一下
## 部分参考代码
C++ 部分参考代码，有注释。
```cpp
for(int i=flag;i>=2;i--){
if(df[i]!=i){//x没有排好
while(df[i]>1){//所处的位置大于1
cout<<df[i]/2<<' '<<df[i]<<'\n';//交换i号位和i/2号位
swap(x[df[i]],x[df[i]/2]);//标记
swap(df[i],df[x[df[i]]]);
}
int high=0;//栈顶
for(int j=i;j>=2;j/=2){//压入栈
t[++high]=j;
t[++high]=1;
}
for(int j=high;j>=2;j--){
cout<<t[j]<<' '<<t[j-1]<<'\n';//交换
swap(x[t[j]],x[t[j-1]]);
swap(df[x[t[j]]],df[x[t[j-1]]]);
}
}
}
```