Luogu10222 [省选联考 2024] 最长待机

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

题意：一个 Sleep++ 程序由 个函数构成，每个函数有一个 flag 和调用列表 ，在调用某个函数时：

  • 若 ，令 ； 若 ，输入变量 。（每次调用都重新输入）
  • 若 为空：等待 秒。 若 不为空：重复以下操作 次：
    • 按顺序调用函数 。（设 的长度为 ）

保证调用关系构成一棵有根树。

我们认为除了“等待 秒“之外的操作（包括输入，调用函数等）都不消耗任何时间。这可能导致同一时刻内输入多个数。

可以证明，调用任意一个 Sleep++ 程序的任意一个函数，无论如何设定输入，消耗的时间总是有限的。

“最长待机”的游戏规则如下：

  • 小 和 小 准备好各自的 Sleep++ 程序并选择各自程序中的一个函数。它们互相知晓对方程序的结构以及选择的函数。

  • 在时刻 ，小 和 小 同时调用自己选择的函数，游戏开始。

  • 在时刻 （），双方可以看到对方在时刻 输入的所有数字，并相应调整自己在时刻 输入的数字，但双方无法得知对方在时刻 输入的数字。

  • 函数调用先结束的一方输掉游戏，另一方胜利。两个调用同时结束算作平局。

小 和 小 都是绝顶聪明的，在它们眼中，如果有一方存在必胜策略，那么这局游戏是不公平的。换言之，双方都不存在必胜策略的游戏是公平的。

小 写了一个 个函数的 Sleep++ 程序并进行了 次操作，操作有以下两种：

  • 操作一：给出 ，将 修改为 ；
  • 操作二：给出 ，与小 玩一局“最长待机”，开始时小 会调用自己的函数 。

小 信奉极简主义，它希望对于每一局游戏设计出函数个数最少的程序，使得选择其中某个函数能让这局游戏是公平的。你能帮它求出最少所需的函数个数吗？

可以证明，小 总是能设计一个程序并选择其中一个函数，使得游戏是公平的。

，，时限 。

分析性质

为了直观，将函数抽象成节点，程序抽象成有根树。 的点称为白点， 的点称为黑点。

  • 对于两棵树 ，若 存在必胜策略，则记 （ 强于 ），若 存在必胜策略，则记 （ 弱于 ），若双方都不存在必胜策略，则记 （ 与 相平）。特殊地，若双方结构完全一致，则记 （ 与 全等）。

显然，等式和不等式的传递性都成立。等号“”将树划分为若干个等价类，我们的目标就是找出等价类中点数最小的树。

  • 引理 1：若某一方必胜，假定对方在时刻 时能观测自己在时刻 时的决策再行动，仍然必胜。（即相同时刻，允许对方后手决策）

证明：略。

  • 引理 2：如果将某个子树换成不弱于它的树，整个结构不会变弱。

证明：记被替换的子树根为 ，记原来的树为 ，替换后的树为 。

考虑 对战时 能否必胜。根据引理1，假设 后手决策， 显然可以模仿使得 在初次访问 之前的决策完全相同。于是两者同时调用 ，由于 替换了不弱的子树，每次在 结束时 的耗时可以不少于 。于是对于 之外的部分， 的每一个决策都可以被 模仿。 的总耗时不少于 。

推论：删除一个子树，结构不会变强。

分析性质 - 全黑点的情况

  • 引理 3：比较两个纯黑链时，长者严格更强。

证明：略。（考虑用长链构造两个短链，第一个用于等待一秒，第二个模仿对方）

  • 引理 4：如果某个黑点的儿子都全等，只保留一个，新结构与原结构相平。

证明：记该节点为 ，原来有 个全等的儿子。化简后，每次调用 打算输入 时输入成 即与原来等价。这说明化简后不弱于化简前。

再根据引理2，化简后不强于化简前，于是相平。

  • 引理 5：纯黑树相平于一条黑链，链长为树的最大深度。

证明：从深到浅，将每个点的较差儿子们都换为最强儿子，使得每个儿子全等，然后由引理 3 只保留一个。这样操作最终得到一条链。

显然，这些操作不会使最大深度增加。且原结构显然不弱于深度相同的链（故强于深度更小的所有链），故最终得到的就是深度相同的链。

分析性质 - 一般情况

  • 引理 6：若白点有父亲有儿子，等价于直接将它删除，并将它的儿子接给父亲。（显然）

  • 定理：若根是黑点，整棵树相平于一条黑链，链长为“从根出发的路径的最大黑点数”。且这是能化简到的最小点数。

证明：首先用引理 6 删除所有非叶白点，注意到单个白点弱于单个黑点，由引理 5 即得。再由引理 3 容易证明这是最小点数。

根是黑点的情况已经解决。对于根是白点的情况，利用引理 6 与其推论进行化简，最终得到只有根是白色，子孙是若干黑链（或单个白叶子，视为“长度为 的黑链”），我们称这种结构为“扫把”。

  • 引理 7：“扫把” 的一个黑链长度为 ，它后面的黑链长度为 ，且 ，将 删除得到“扫把”，则 相平。

证明：根据引理 2， 显然不能变强。考虑 对战，允许 后手决策， 模仿 的策略，但每次打算填写 链时，将 填成 （额外展开出一个长度为 的链）则不弱于 。

推论：“扫把”可以只保留黑链长度的前缀最大值。

根据上述引理，我们可以将任意一棵树化简为黑链长度单调不降的扫把。

  • 定理：化简后不同的结构不相平，具体地，后缀字典序更大者强。

证明：设 为两个化简后的结构（本质上是黑链长序列 ），从后往前找到两个序列的第一个不同之处 ，假设 ，将 全部丢弃（由引理 2，B 不会变强）。将链 的第一个输入填写为 ，则展开成 条长度为 的链条。前 条链至少和 相平，多余的一条链至少可以拖一秒。之后模仿 的操作即可。

特殊地，若 是 的后缀，则 用 前面多出来的部分至少拖一秒，之后模仿 的操作即可。

显然，化简后的结构点数是最小的。

推论：从最开始调用的点开始搜索出一个白连通块，将这个连通块的直接子树按照 dfs 序从左到右排列为 ，记 为 的“从根出发的路径的最大黑点数”，则小 所需的最小点数为 的前缀最大值之和。

特殊地，单个白点虽然记为 但贡献为 ，若 则可省去根白点。

数据结构维护

先写出朴素 DP。

  • 记 为 子树“从根出发的路径的最大黑点数”
  • 定义序列 ：从 搜索出一个白连通块（可能为空），将这个连通块的直接儿子按照 dfs 序从左到右排列为 ，则 。
    询问 点时， 的和即为答案。

下面考虑转移。 是简单的，只考虑 的转移。

  • 若 是白点：将各个儿子的 相接，取出所有前缀最大值，即为 。
  • 若 是黑点：。

接下来用数据结构维护。

首先由引理 6，可以新建 个永久白点将树三度化。（免去用数据结构维护多个儿子）

将树重链剖分，然后考虑每条重链，将轻儿子的共线视为定值，将转移写成有结合律的形式，DDP 维护即可。

然而，序列 的长度可能达到 级别导致复杂度退化。此处有一个自然根号：注意到 中元素总和不超过子树大小，前缀最大值只有根号种，于是将 中相邻相等的部分缩起来就只需要 的信息。

用全局平衡二叉树维护，操作时涉及到的点个数为 ， 序列压缩后长度为 ，其和为 。故时间复杂度 ，类似可证空间 。

注：类似楼房重建，存在 poly log 做法，但在效率和实现难度上似乎不如根号。