题解：P6324 [COCI 2006/2007 #4] JOGURT

· · 题解

找到规律后就性质勃勃来写题解了。

所以我真的推荐多用用画图或者草稿纸画一下特解找规律。

我的规律：根节点为 1，让每个节点的左右子节点分别为当前节点加上 2^{dep} 和 2^{dep+1} 的值。如果遍历到了叶子节点，记录叶子节点的下标，最后反转叶子节点的下标。

值的唯一性原因就是每一次递归都是将当前数列对半分开，每一个值肯定就是唯一的了。

最后一层相邻节点相差一定满足条件，左节点减去右节点的值 2^{dep}-2^{dep+1}=-2^{dep}。

向上回退，然后你会发现上一层的左右节点相差 2^{dep+1}-2^{dep}=2^{dep}，（这个时候 dep 比上一步小一啊！这个时候最后一层的差值为 2^{dep+1}-2^{dep+2}=-2^{dep+1} 了。）这个时候定睛一看喵，两层 6 个节点的差值刚好 -2^{dep+1}+2^{dep}=-2^{dep}，满足条件！

而且不断向上递归，每一层由于左节点小于右节点，留下 2^{dep} 的差，但是由于叶子节点是逆序的，留下了丰厚的家底，左右节点传递上来足足 -2^{dep+1} 的差，正负抵消结算得到 -2^{dep} 的差，好了，完美。

感觉其实扯了一堆废话，大白话就是子节点刚好差了 2 的 dep 次方，向上每一次逐渐减半，好了。

void dfs(ll val,ll dep)
{
    //记录前序遍历
    ans.emplace_back(val);
    //叶子节点处理
    if(dep==n-1)
    {
        lp.emplace_back(ans.size()-1);//leaf_pos 我可真是英语甜菜！
        return;
    }
    //遍历
    dfs(val+(1LL<<dep),dep+1);
    dfs(val+(1LL<<(dep+1)),dep+1);
}
cin >> n;
//从第 0 层开始遍历
dfs(1,0);
//开始反转叶子节点
ll L=0,R=lp.size()-1;
while(L<R)swap(ans[lp[L++]],ans[lp[R--]]);
//输出答案
for(ll i:ans) cout << i << ' ';

//WA 了一发才过，不嘻嘻
/*
后记预告：
OMG 情けない 最早
バイバイバイバイバイしたい
脳内も予測不能 故に
解解解解解は無い
*/

其实一开始我还找到一种开头为最大值的写法，奈何不知道具体实现方式。

n=1 3 1 2
n=2 7 6 1 3 5 2 4
n=3 15 13 11 1 5 9 3 7 14 12 2 6 10 4 8

这一种做法让剩下的数中较小的值先铺下最下层，奈何实现没有想出，AI 写了一团胡言乱语，希望有人可以找到实现。