自动搬运

查看原文

来自洛谷，原作者为

	Ted_LightningTechG_ **

搬运于2025-08-24 22:19:40，当前版本为作者最后更新于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;
}