NOI2024联合省选 第二试

NOI2024联合省选 第二试 时间:2024年3月3日08:30~1300 题目名称 迷宫守卫 重塑时光 最长待机 传统型 题日类型 传统型 传统型 目录 maze timeline sleep maze timeline 可执行文件名 sleep 输入文件名 maze.in timeline.in s1eep.in maze.out timeline.out 输出文件名 sleep.out 每个测试点时限 0.5秒 1.5秒 2.0秒 内存限制 512MiB 1024 MiB 1024 MiB 2 测试点数日 20 25 测试点是否等分 是 是 提交源程序文件名 对于C++ 语言maze.cpp timeline.cpp sleep.cpp 编译选项 对于C++ 语言 -02 -std=c++14-static 注意事项(请仔细阅读) 1. 文件名(程序名和输入输出文件名)必须使用英文小写。 2. C/C++中函数main0的返回值类型必须是int.程序正常结束时的返回值必须 是0。 3. 提交的程序代码文件的放置位置请参考各省的具体要求。 4. 因违反以上三点而出现的错误或问题,申诉时一律不予受理。 5. 若无特殊说明,结果的比较方式为全文比较(过滤行末空格及文末回车). 6. 选手提交的程序源文件必须不大于100KB。 7. 程序可使用的栈空间内存限制与题目的内存限制一致。 8. 全国统一评测时采用的机器配置为:Intel(R)Core(TM)i7-4790 CPUo 3.60GHz. 内存16GB。上述时限以此配置为准。 9. 只提供Linux格式附加样例文件。 10. 评测在当前最新公布的NOILinux下进行,各语言的编译器版本以此为准。 NO12024联合省选 第二试迷宫守卫(maze) 迷宫守卫 (maze) 【题目描述】 Alice拥有一座迷宫,这座迷宫可以抽象成一棵拥有2”个叶节点的满二又树,总节 点数目为(2n1-1):依次编号为1~(2+1-1)。其中编号为2~(2*1-1)的是叶 节点,编号为1~(2”-1)的是非叶节点,且非叶节点1 “ (2-1)的左儿子编号 为2u,右儿子编号为(2u+1)。 每个非叶节点都有一个石像守卫,初始时,所有石像守卫均在沉睡。唤醒“点的石 像守卫需要r.的魔力值。 每个叶节点都有一个符文,点的符文记作。保证r.r+1...42-.-:构成 1~2的排列。 探险者初始时持有空序列Q,从节点1出发,按照如下规则行动: · 到达叶节点v时,将v点的符文a.添加到序列Q的末尾,然后返回父节点。 .到达非叶节点时: 一若该点的石像守卫已被唤醒,则只能先前往左儿子,(从左儿子返回后)再 前往右儿子,(从右儿子返回后)最后返回父节点。 一若该点的石像守卫在沉睡,可以在以下二者中任选其一: ·先前往左儿子,再前往右儿子,最后返回父节点。 .先前往右儿子,再前往左儿子,最后返回父节点。 返回节点1时,探险结束。可以证明,探险者一定访问每个叶节点各一次,故此时 Q的长度为2。 探险者Bob准备进入迷宫,他希望探险结束时的Q的字典序越小越好,与之相对, Alice希望Q的字典序越大越好。 在Bob出发之前,Alice可以选择一些魔力值花费之和不超过K的石像守卫,并唤 醒它们。Bob出发时,他能够知道Alice唤醒了哪些神像。若双方都采取最优策略,求 序列Q的最终取值。 对于两个长度为2”的序列Q.Q.称Q:字典序小于Q。当且仅当以下条件成立 ·E1.2满足以下两个条件: -Vj<i.Q=Q: -QQ. 【输入格式】 从文件maze.in中读入数据。 本题有多组测试数据。输入的第一行包含一个正整数T,表示测试数据组数 接下来依次7组测试数据。对于每组测试数据: 第2声 共12页 NO12024联合省选 第二试迷宫守卫(maze) · 第一行两个整数n.K表示迷宫规模和Alice可用于唤醒石像守卫的魔力值上限. ·第二行(2”-1)个整数n...,u2-:表示唤醒各个石像守卫耗费的魔力值。 .第三行2”个整数-+1..--:表示各个叶节点上的符文。 【输出格式】 输出到文件maze.out中。 对于每组数据,输出一行2”个整数。:.Q。.....Q,表示双方都采取最优策略的 情况下,序列Q的最终取值。 【样例1输入】 11 3212121 42637158 【样例1输出】 一将来 24635871 【样例1解释】 ·第一组数据中,Alice无法唤醒石像守卫,Bob可以选择先访问叶节点3.再访问 叶节点2,得Q=(1.2。 ·第二组数据中,Alice可以唤醒节点1的石像守卫,Bob只能先访问叶节点2,再 访问叶节点3,得Q=(2.1. · 第三组数据中:Alice的最优策略是唤醒节点5.6的石