#PQJ1543x8324. QOJ 1543_8324
QOJ 1543_8324
NOI2024 联合省选 第二试迷宫守卫(maze) 迷宫守卫(maze) 【题目描述】 Alice 拥有一座迷宫,这座迷宫可以抽象成一棵拥有2n 个叶节点的满二叉树,总节 点数目为(2n+1 −1),依次编号为1 ∼(2n+1 −1)。其中编号为2n ∼(2n+1 −1) 的是叶 节点,编号为1 ∼(2n −1) 的是非叶节点,且非叶节点1 ≤u ≤(2n −1) 的左儿子编号 为2u,右儿子编号为(2u + 1)。 每个非叶节点都有一个石像守卫,初始时,所有石像守卫均在沉睡。唤醒u 点的石 像守卫需要wu 的魔力值。 每个叶节点都有一个符文,v 点的符文记作qv。.保.证q2n, q2n+1, · · · , q2n+1−1 .构.成 1 ∼2n .的.排.列。 探险者初始时持有空序列Q,从节点1 出发,按照如下规则行动: • 到达叶节点v 时,将v 点的符文qv 添加到序列Q 的末尾,然后返回父节点。 • 到达非叶节点u 时: – 若该点的石像守卫已被唤醒,则只能先前往左儿子,(从左儿子返回后)再 前往右儿子,(从右儿子返回后)最后返回父节点。 – 若该点的石像守卫在沉睡,可以在以下二者中任选其一: ∗先前往左儿子,再前往右儿子,最后返回父节点。 ∗先前往右儿子,再前往左儿子,最后返回父节点。 返回节点1 时,探险结束。可以证明,探险者一定访问每个叶节点各一次,故此时 Q 的长度为2n。 探险者Bob 准备进入迷宫,他希望探险结束时的Q 的字典序越小越好,与之相对, Alice 希望Q 的字典序越大越好。 在Bob 出发之前,Alice 可以选择一些魔力值花费之和不超过K 的石像守卫,并唤 醒它们。Bob 出发时,他能够知道Alice 唤醒了哪些神像。若.双.方.都.采.取.最.优.策.略,求 序列Q 的最终取值。 对于两个长度为2n 的序列Q1, Q2,称Q1 字典序小于Q2 当且仅当以下条件成立: • ∃i ∈[1, 2n] 满足以下两个条件: – ∀1 ≤j < i,Q1,j = Q2,j; – Q1,i < Q2,i。 【输入格式】 从文件maze.in 中读入数据。 .本.题.有.多.组.测.试.数.据。输入的第一行包含一个正整数T,表示测试数据组数。 接下来依次T 组测试数据。对于每组测试数据: 第2 页 共12 页
NOI2024 联合省选 第二试迷宫守卫(maze) • 第一行两个整数n, K 表示迷宫规模和Alice 可用于唤醒石像守卫的魔力值上限。 • 第二行(2n −1) 个整数w1, w2, · · · , w2n−1 表示唤醒各个石像守卫耗费的魔力值。 • 第三行2n 个整数q2n, q2n+1, · · · , q2n+1−1 表示各个叶节点上的符文。 【输出格式】 输出到文件maze.out 中。 对于每组数据,输出一行2n 个整数Q1, Q2, · · · , Q2n,表示双方都采取最优策略的 情况下,序列Q 的最终取值。 【样例1 输入】 1 3 2 1 0 3 1 4 2 1 5 1 1 6 1 7 2 1 8 3 3 9 3 2 1 2 1 2 1 10 4 2 6 3 7 1 5 8 【样例1 输出】 1 1 2 2 2 1 3 2 4 6 3 5 8 7 1 【样例1 解释】 • 第一组数据中,Alice 无法唤醒石像守卫,Bob 可以选择先访问叶节点3,再访问 叶节点2,得Q = {1, 2}。 • 第二组数据中,Alice 可以唤醒节点1 的石像守卫,Bob 只能先访问叶节点2,再 访问叶节点3,得Q = {2, 1}。 • 第三组数据中,Alice 的最优策略是唤醒节点5, 6 的石像守卫。 第3 页 共12 页
NOI2024 联合省选 第二试迷宫守卫(maze) 【样例2】 见选手目录下的maze/maze2.in 与maze/maze2.ans。 该组数据满足特殊性质A。 【样例3】 见选手目录下的maze/maze3.in 与maze/maze3.ans。 该组数据满足特殊性质B。 【样例4】 见选手目录下的maze/maze4.in 与maze/maze4.ans。 【样例5】 见选手目录下的maze/maze5.in 与maze/maze5.ans。 【子任务】 设! 2n 表示单个测试点中所有测试数据的2n 的和。对于所有测试数据,保证 • 1 ≤T ≤100; • 1 ≤n ≤16,1 ≤! 2n ≤105; • 0 ≤K ≤1012; • ∀1 ≤u ≤(2n −1),0 ≤wu ≤1012; • q2n, q2n+1, · · · , q2n+1−1 构成1 ∼2n 的排列。 测试点编号 n ≤ ! 2n ≤ 特殊性质 1 ∼5 4 80 无 6 6 200 A 7 ∼8 B 9 ∼10 无 11 11 4000 A 12 ∼13 B 14 ∼15 无 16 16 105 A 17 ∼18 B 19 ∼20 无 特殊性质A:∀2n ≤v ≤(2n+1 −1),qv = (2n+1 −v)。 特殊性质B:∀1 ≤u ≤(2n −1),wu = 1。 第4 页 共12 页