Luogu10220 [省选联考 2024] 迷宫守卫

发表于 分类于 ， ， 阅读次数：

题意：Alice 拥有一座迷宫，这座迷宫可以抽象成一棵拥有 个叶节点的满二叉树，总节点数为 ，节点编号为 。其中，编号为 的是叶节点，编号为 的是非叶节点，且满足对于非叶节点 （），其左儿子编号为 ，右儿子编号为 。

每个非叶节点都有一个石像守卫，初始时，所有石像守卫均未启动。启动 点的石像守卫需要 的魔力值。

每个叶节点都有一个符文，用正整数表示， 点的符文记作 。保证 构成 的排列。

探险者初始时持有空序列 ，从节点 出发，按照如下规则行动：

  • 到达叶节点 时，将 点的符文 添加到序列 的末尾，然后返回父节点。

  • 到达非叶节点 时：

    • 若石像守卫已启动，则先前往左儿子，（从左儿子返回后）再前往右儿子，（从右儿子返回后）最后返回父节点。

    • 若石像守卫未启动，可以在以下二者中任选其一：

      • 先前往左儿子，再前往右儿子，最后返回父节点。

      • 先前往右儿子，再前往左儿子，最后返回父节点。

返回节点 时，探险结束。可以证明，探险者一定访问每个叶节点各一次，故此时 的长度为 。

探险者 Bob 准备进入迷宫，他希望探险结束时的 的字典序越小越好，与之相对，Alice 希望 的字典序越大越好。

在 Bob 出发之前，Alice 可以选择一些魔力值花费之和不超过 的石像守卫，并启动它们，Bob 可以得知启动了那些守卫。若双方都采取最优策略，求序列 的最终取值。

多组数据，，，，，时限 。

  • 加强版：不保证树是满二叉树，可能是很深的一般二叉树。

函数 求出在 的子树中有 的费用可供标记一些点，所能得到的字典序最大的 ，以及在此基础上所消耗的最小费用。

首先最大化 的首位，二分判定首位是否能大于等于 。

记 表示在 的子树内标记一些点，使得 dfs 序首位大于等于 的最小花费，边界显然。记 的左右儿子为 ，有转移：

于是可以求出 首位的取值。记为了保证 首位所花费的费用为 。

找出 首位对应的叶子 ，Bob 在最开始时一定走的是 到 的链，这条链的分支子树构成若干子问题（需要按顺序考虑）。

考虑分支 ，它的父亲为 ，若 是左儿子，跑 ，并减少对应费用。

若 是右儿子：

  • 若 ，则原来的方案选择了“标记 点”。考虑能否换成“使 子树安全”，判断 是否大于等于 ，如果是，跑 ；如果不是，跑 。

  • 否则，跑 。

复杂度 。

考虑优化，记 表示判定分界为 时 dp 数组的取值，只需要 次查询即可完成本题。

可持久化 ddp 维护 即可。

时间复杂度 ，空间复杂度 。其中 是总点数。

当然，这太无趣了（而且考点重复），为了避免考 ddp，把树出成满二叉树就行。这样暴力就能过了。