Whisper-6's Blog!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，，时限 。

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

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

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

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

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

• 到达非叶节点 时：

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

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

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

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

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

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

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

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

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

题意：对于长度为 的序列 ，定义 为将下标模 等于 的位置抽出组成的序列，保证 ，即 。

对于序列 定义权值函数 ： 现在给出长为 的序列 ，求 。

答案对 取模，时限 。

• 原题：
• 加强版：

你无需考虑输入序列 的耗时。

题意：给出长为 的排列，每次可以交换相邻两个位置。

设 为使排列中存在连续子序列 的最少操作次数。

求出 。

，时限 。

题意：给出一个 行 列的矩阵，可以对列进行循环移位，最后的贡献是每一行的最大值的和。

最大化贡献。

多组数据，，，，时限 。

题意：给出两棵树 ，有边权，点的标号对应。

生成无向图 ， 之间的边权为 。

求这张图的最小生成树的边权和，，时限 。

题意 : 给定一棵 个点的树 ，边有边权，点有点权 。

建立一张完全图 ， 之间的边长为

求完全图的最小生成树边权和。

，时限 。

题意：给出一张 个点 条边的简单无向图，点编号为 。

有若干个询问，给出 ，判定是否存在一条路径满足：

• 起点为 ，终点为 。

• 存在途经点 （路径写作 ），使得 不经过编号为 的点， 不经过编号为 的点。（点 被限制两次）

强制在线。，，时限 。

题意：给定一个序列 ，求其 个非空子序列的 的和。

答案对给定的大质数取模，，，时限 。

题意：给出一棵 个点的无根树，点有点权 ，边有边权，均非负。

求一个点 使得 最小。

，时限 。