P6324 [COCI2006-2007#4] JOGURT 题解

Ted_LightningTechG_ · 2023-09-24 11:01:44 · 题解

\mathbf{0x01} 题目思路

这是道找规律的好题。我们先来构建一棵四层的树。

          15
    14          13

 12    10    11    9

1  5  3  7  2  6  4  8

没规律啊！

来，我们把它变一变：将最后一行的顺序倒过来，维持每一行大致呈下降趋势。

          15
    14          13

 12    10    11    9

8  4  6  2  7  3  5  1

然而，这好像还是不太有规律。再来一次，将每一行最小的数变为 1，同行的其它数也减去相同的数：

          1
    2          1

 4     2    3     1

8  4  6  2  7  3  5  1

规律来咯！

对于每一行，我们都可以这么来构造，以第 3 行为例

先是一个 1：

1

复制一下，把复制出来的放到左侧，然后加 4：

5 1

再复制，把复制出来的放到左侧，加 2：

7 3 5 1

重复操作，直至这行满了：

8 4 6 2 7 3 5 1

我们发现，每行的构造方式几乎一致，但是每次复制时加的数有些不同，我列张表：

不难看出第 n 行第一次加 2^{n - 2}。

好了，树建好了，但是这棵树不太对的样子。别忘了我们可是做过 2 次操作的，所以再把它变回去。

我们选择倒推，还记得我们第二次干了什么吗？我们减掉了一个特定的数值。然而，我们现在不知道到底减了多少。我们回头康一康：

          15
    14          13

 12    10    11    9

8  4  6  2  7  3  5  1

          1
    2          1

 4     2    3     1

8  4  6  2  7  3  5  1

第一行，减了 14；

第二行，减了 12；

第三行，减了 8；

第四行，减了 1。

如果说这样看不出什么的话，你可以看看整棵树。没错！每次减掉的就是当前行以下所有元素的个数。

然后，还记得我们第一次干了什么吗？我们逆序了最后一行。这个就不用我多说了吧。

最后的最后，还有一个先序输出。由于我把树存在了数组里，所以有些麻烦，具体操作细节在代码里展示。

\mathbf{0x02} 代码

#include<bits/stdc++.h>
//using namespace std;
int n;
int node[20][60000], ans[20][60000];
void dfs(int L, int len, int floor, int minus) {//对每行的建树，建完顺便放入node
    if( len == 1 ) {
        node[floor][L] = ( 1 << floor - 1 );
        return; 
    }
    int hlf = (len >> 1), tot = 1 << floor - 1;
    dfs( L + hlf, hlf, floor, minus << 1);
    int mid = hlf + L - 1;
    for(int i = L; i <= mid; i ++) node[floor][i] = node[floor][i + hlf] - minus;
}
void print(int x, int y) {
    if( x == n ) {//若到了第n行，那就直接输出，返回
        std::cout << ans[x][y] <<' ';
        return;
    }
    std::cout << ans[x][y] <<' ';//输出当前的数，即根
    print( x + 1, (y << 1) - 1 );//跳至左子树的根，位于ans[x+1][(y<<1)-1]，进行递归，即左
    print( x + 1, y << 1 );//同左子树，这里是右
}
int main() {
    std::cin >> n;
    for(int i = n; i > 0; i --) 
        dfs( 1, 1 << i - 1, i, 1 ); //建树并存入node
    int num = 0;
   //将树还原
    for(int i = n; i >= 1; i --) {//把变形时减掉的数字加上
        for(int j = 1; j <= ( 1 << i - 1 ); j ++) 
            node[i][j] += num;
        num += ( 1 << i - 1 );
    }
    for(int i = 1; i < n; i ++) //把顺序转正，存入ans
        for(int j = 1; j <= ( 1 << i - 1 ); j ++) 
            ans[i][j] = node[i][( 1 << i - 1 ) - j + 1];
    for(int i = 1; i <= ( 1 << n - 1 ); i ++) ans[n][i] = node[n][i];
    print(1, 1);//先序输出
    return 0;
}