A6644. 「联合省选 2024」迷宫守卫
编程题
省选/NOI-
知识点
题目描述
Alice 拥有一座迷宫，这座迷宫可以抽象成一棵拥有 $2^n$ 个叶节点的满二叉树，总节点数目为 $(2^{n+1} − 1)$，依次编号为 $1 \sim (2^{n+1} − 1)$。其中编号为 $2^n \sim (2^{n+1} − 1)$ 的是叶节点，编号为 $1 \sim (2^n − 1)$ 的是非叶节点，且非叶节点 $1 \le u \le (2^n − 1)$ 的左儿子编号为 $2u$，右儿子编号为 $(2u + 1)$。
每个非叶节点都有一个石像守卫，初始时，所有石像守卫均在沉睡。唤醒 $u$ 点的石像守卫需要 $w_u$ 的魔力值。
每个叶节点都有一个符文，$v$ 点的符文记作 $q_v$。**保证$q_{2^n}, q_{2^n+1},\cdots, q_{2^{n+1}−1}$ 构成 $1 \sim 2^n$ 的排列**。
探险者初始时持有空序列 $Q$，从节点 $1$ 出发，按照如下规则行动：
- 到达叶节点 $v$ 时，将 $v$ 点的符文 $q_v$ 添加到序列 $Q$ 的末尾，然后返回父节点。
- 到达非叶节点 $u$ 时：
- 若该点的石像守卫已被唤醒，则只能先前往左儿子，（从左儿子返回后）再前往右儿子，（从右儿子返回后）最后返回父节点。
- 若该点的石像守卫在沉睡，可以在以下二者中任选其一：
- 先前往左儿子，再前往右儿子，最后返回父节点。
- 先前往右儿子，再前往左儿子，最后返回父节点。
返回节点 $1$ 时，探险结束。可以证明，探险者一定访问每个叶节点各一次，故此时 $Q$ 的长度为 $2^n$。
探险者 Bob 准备进入迷宫，他希望探险结束时的 $Q$ 的字典序越小越好，与之相对，Alice 希望 $Q$ 的字典序越大越好。
在Bob 出发之前，Alice 可以选择一些魔力值花费之和不超过 $K$ 的石像守卫，并唤醒它们。Bob 出发时，他能够知道 Alice 唤醒了哪些神像。若**双方都采取最优策略**，求序列 $Q$ 的最终取值。
对于两个长度为 $2^n$ 的序列 $Q_1,Q_2$，称 $Q_1$ 字典序小于 $Q_2$ 当且仅当以下条件成立：
- $\exists i \in [1, 2n]$ 满足以下两个条件：
- $\forall 1 \le j < i，Q_{1,j} = Q_{2,j}$；
- $Q_{1,i} < Q_{2,i}$。
每个非叶节点都有一个石像守卫，初始时，所有石像守卫均在沉睡。唤醒 $u$ 点的石像守卫需要 $w_u$ 的魔力值。
每个叶节点都有一个符文，$v$ 点的符文记作 $q_v$。**保证$q_{2^n}, q_{2^n+1},\cdots, q_{2^{n+1}−1}$ 构成 $1 \sim 2^n$ 的排列**。
探险者初始时持有空序列 $Q$，从节点 $1$ 出发，按照如下规则行动：
- 到达叶节点 $v$ 时，将 $v$ 点的符文 $q_v$ 添加到序列 $Q$ 的末尾，然后返回父节点。
- 到达非叶节点 $u$ 时：
- 若该点的石像守卫已被唤醒，则只能先前往左儿子，（从左儿子返回后）再前往右儿子，（从右儿子返回后）最后返回父节点。
- 若该点的石像守卫在沉睡，可以在以下二者中任选其一：
- 先前往左儿子，再前往右儿子，最后返回父节点。
- 先前往右儿子，再前往左儿子，最后返回父节点。
返回节点 $1$ 时，探险结束。可以证明，探险者一定访问每个叶节点各一次，故此时 $Q$ 的长度为 $2^n$。
探险者 Bob 准备进入迷宫，他希望探险结束时的 $Q$ 的字典序越小越好，与之相对，Alice 希望 $Q$ 的字典序越大越好。
在Bob 出发之前，Alice 可以选择一些魔力值花费之和不超过 $K$ 的石像守卫，并唤醒它们。Bob 出发时，他能够知道 Alice 唤醒了哪些神像。若**双方都采取最优策略**，求序列 $Q$ 的最终取值。
对于两个长度为 $2^n$ 的序列 $Q_1,Q_2$，称 $Q_1$ 字典序小于 $Q_2$ 当且仅当以下条件成立：
- $\exists i \in [1, 2n]$ 满足以下两个条件：
- $\forall 1 \le j < i，Q_{1,j} = Q_{2,j}$；
- $Q_{1,i} < Q_{2,i}$。
输入格式
从文件
**本题有多组测试数据**。输入的第一行包含一个正整数 $T$，表示测试数据组数。
接下来依次 $T$ 组测试数据。对于每组测试数据：
- 第一行两个整数 $n,K$ 表示迷宫规模和 Alice 可用于唤醒石像守卫的魔力值上限。
- 第二行 $(2^n − 1)$ 个整数 $w_1,w_2,\cdots,w_{2^n−1}$ 表示唤醒各个石像守卫耗费的魔力值。
- 第三行 $2^n$ 个整数 $q_{2^n}, q_{2^n+1},\cdots, q_{2^{n+1}−1}$ 表示各个叶节点上的符文。
maze.in 中读入数据。**本题有多组测试数据**。输入的第一行包含一个正整数 $T$，表示测试数据组数。
接下来依次 $T$ 组测试数据。对于每组测试数据：
- 第一行两个整数 $n,K$ 表示迷宫规模和 Alice 可用于唤醒石像守卫的魔力值上限。
- 第二行 $(2^n − 1)$ 个整数 $w_1,w_2,\cdots,w_{2^n−1}$ 表示唤醒各个石像守卫耗费的魔力值。
- 第三行 $2^n$ 个整数 $q_{2^n}, q_{2^n+1},\cdots, q_{2^{n+1}−1}$ 表示各个叶节点上的符文。
输出格式
输出到文件
对于每组数据，输出一行 $2^n$ 个整数 $Q_1,Q_2,\cdots,Q_{2^n}$，表示双方都采取最优策略的情况下，序列 $Q$ 的最终取值。
maze.out 中。对于每组数据，输出一行 $2^n$ 个整数 $Q_1,Q_2,\cdots,Q_{2^n}$，表示双方都采取最优策略的情况下，序列 $Q$ 的最终取值。
输入输出样例
输入 #1
3 1 0 1 2 1 1 1 1 2 1 3 3 3 2 1 2 1 2 1 4 2 6 3 7 1 5 8
输出 #1
1 2 2 1 2 4 6 3 5 8 7 1
说明/提示
设 $\sum 2^n$ 表示单个测试点钟所有测试数据的 $2^n$ 的和。对于所有测试数据，保证
- $1\le T \le 100$；
- $1\le n \le 16$，$1 \le \sum 2^n \le 10^5$；
- $0\le K \le 10^{12}$
- $\forall 1 \le u \le (2^n-1)$，$0 \le w_u \le 10^{12}$；
- $q_{2^n},q_{2^n+1},\cdots,q_{2^{n+1}-1}$ 构成 $1\sim 2^n$ 的排列。
| 测试点编号 | $n\le$ | $\sum 2^n \le$ | 特殊性质 |
| :--: | :--: | :--: | :--: |
| $1\sim 5$ | $4$ | $80$ | 无 |
| $6$ | $6$ | $200$ | A |
| $7\sim 8$ | $6$ | $200$ | B |
| $9\sim 10$ | $6$ | $200$ | 无 |
| $11$ | $11$ | $4000$ | A |
| $12\sim 13$ | $11$ | $4000$ | B |
| $14\sim 15$ | $11$ | $4000$ | 无 |
| $16$ | $16$ | $10^5$ | A |
| $17\sim 18$ | $16$ | $10^5$ | B |
| $19\sim 20$ | $16$ | $10^5$ | 无 |
特殊性质 A：$\forall 2^n \le v \le (2^{n+1}-1)$，$q_v = (2^{n+1}-v)$。
特殊性质 B：$\forall 1 \le u \le (2^n-1)$，$w_u = 1$。
- $1\le T \le 100$；
- $1\le n \le 16$，$1 \le \sum 2^n \le 10^5$；
- $0\le K \le 10^{12}$
- $\forall 1 \le u \le (2^n-1)$，$0 \le w_u \le 10^{12}$；
- $q_{2^n},q_{2^n+1},\cdots,q_{2^{n+1}-1}$ 构成 $1\sim 2^n$ 的排列。
| 测试点编号 | $n\le$ | $\sum 2^n \le$ | 特殊性质 |
| :--: | :--: | :--: | :--: |
| $1\sim 5$ | $4$ | $80$ | 无 |
| $6$ | $6$ | $200$ | A |
| $7\sim 8$ | $6$ | $200$ | B |
| $9\sim 10$ | $6$ | $200$ | 无 |
| $11$ | $11$ | $4000$ | A |
| $12\sim 13$ | $11$ | $4000$ | B |
| $14\sim 15$ | $11$ | $4000$ | 无 |
| $16$ | $16$ | $10^5$ | A |
| $17\sim 18$ | $16$ | $10^5$ | B |
| $19\sim 20$ | $16$ | $10^5$ | 无 |
特殊性质 A：$\forall 2^n \le v \le (2^{n+1}-1)$，$q_v = (2^{n+1}-v)$。
特殊性质 B：$\forall 1 \le u \le (2^n-1)$，$w_u = 1$。