A 动态树

Idea: 沃若，Solution: FR (negiizhao)

设当前的唯一直径为 。初始时，。

当 时，唯一直径变为 ； 时，唯一直径变为 。否则，直径不会变得更长。

接着，可以通过反证法（或观察）得到如下结论：加入叶子节点 后，若直径不再唯一，新直径一定是 或 。

于是我们只需要在动态加叶子的同时，询问其到原先的直径端点的距离即可。

树上两点间距离若通过倍增 LCA 求解，就可以支持在线加点并处理询问了。

总时间复杂度为 。

B Sang 的奇妙冒险

Idea & Solution: Sang，Developer: 沃若

根据绝对值不等式，最小代价必然是直接从第 个元素移动到第 个元素，即 。如果这里不理解，可以继续往下看。

假设 ，考虑求解最大移动次数：首先，不可能经过严格小于 或严格大于 的元素，否则代价一定会变大（例如 比 的代价大）。所以我们只需要保留介于 区间内的元素。

接着，每一步只能往更大的元素移动，否则代价也会变大（例如 比 的代价大）。于是转化为最长不下降子序列问题。

若 ，可以转化为最长不上升子序列问题。实现时可以看成从第 个元素移动到第 个元素，直接翻转 后直接沿用上述方法求解。由于是取绝对值，答案不会改变。

总时间复杂度为 。

C 采矿

Idea & Solution: 寒鸽儿

有个显然的想法：对于老板的监工，被抓住的概率只和下矿天数有关，和具体下矿日期无关。

因此就变成了两个部分：对于某一个下矿天数 ，求 天下矿的最大期望收益和 天下矿不被监工发现的概率，相乘就是下矿 天的最大期望收益。然后从 枚举下矿天数，可得最大期望收益。

对于前者，可以设 表示对于前 天，下矿 次的期望最大收益。一般地，有：

可以直接动态规划求解，注意边界即可。

对于后者，考虑使用古典概型求解。设 表示下矿 天监工 天不被发现的概率，有：

计算时，可以利用如下关系进行递推：

实现时，还需要注意边界：

部分提交的实现方式精度误差较高，需要使用 long double 才能通过。

总时间复杂度为 。

D 在此同步

Idea & Solution: 沃若

对于 及 的排列，显然无解。

有重要观察：交换两个相邻位置的元素，逆序对数只会增加 或减少 。接着考虑如下构造：

找到一个位置 使得 比 和 两者都大（或都小），重排 使这三者间的逆序对数（可能是 或 ）不变。

对于所有其他元素来说，它们之间的相对位置不会改变，与这三个元素的也不会改变，所以总逆序对数不变。

实现时，如果 的大小介于 和 之间，则将 移动到 之后即可。

否则，将 移动到 之前即可。

除了单调递增或递减的排列必然无解，这样的位置 是一定存在的，于是问题解决。

总时间复杂度为 。

E 外接圆

Idea: 沃若，Solution: PinkieRabbit

首先，可以对重复坐标的点去重，并记录它们出现的次数。

若去重后的点数不超过 ，则说明所有点已经共圆，输出 即可。

否则，枚举所有 个不同坐标的点的组合。钦定这三个点（及相同坐标的重复点）不动，并确定一个圆，其他点若不在圆上则需要移动。

需要注意的是：若选择的三点共线，则无法用来确定一个圆，这种情况直接跳过即可。这样做的正确性在于：一定可以用另一个不在直线上的点替换掉它们之一，且答案不会更劣。

对所有的选择方法求最小值，即为答案。若所有点都共线，则指定出现次数最多的 个点不动，其他所有点移动到（同一个）任意不在直线上的点即可。

总时间复杂度为 。

F 任务安排

Idea & Solution: 沃若

拓扑排序模板题的小变形，可以稍加改动 Kahn 算法贪心求解：

第一步：尽可能地进行一遍拓扑排序，但不取任何序列 中的点。

第二步：按顺序去取序列 中的点。

第三步：对剩下的点再进行一遍拓扑排序。

如果在第二步中遇到不能取（入度不为 ）的点，或第三步后依然没有取完所有点，则一定无解。否则取点的顺序即为一个符合条件的构造。

这一构造的必要性及充分性的证明都不困难，此处略，读者可以自行尝试。

总时间复杂度为 。

G 动态二叉树

Idea & Solution: 沃若

考虑离线求解：

先建出最终的二叉树，然后对所有节点重新按 BFS 序编号，并记录深度（即所在层）和对应的原始编号。此时右侧第一个节点即为同层节点中 BFS 序大于询问点且最小的点。

于是，我们可以维护一个平衡树，保存当前所有已经插入到二叉树中的点。

对于第一类操作，只需要在平衡树中查询后继，并检查是否同层即可。

对于第二类操作，将该点的 BFS 序编号插入平衡树中即可。

在 C++ 语言中，利用 STL 提供的 std::set 模板及其中的 set::upper_bound 函数即可方便地实现本题。

总时间复杂度为 。

H 数学

Idea & Solution: 寒鸽儿

根据四平方和定理（或打表），可以知道（或猜想）任意正整数均可表示为不超过 个整数的平方和。

对于分解为 的数（即完全平方数），可以用 的时间枚举得到。

对于分解为 的数，可以分别枚举构成它的两个平方数，时间复杂度 。

对于分解为 的数，可以参照上面的方法在 的时间内求出。

其余数字都分解为 。

当然，也可以直接对完全平方数做背包 DP 求解。

总时间复杂度为 。

I 电梯调度

Idea & Solution: 寒鸽儿

对不起，题面过于考验选手阅读理解。

模拟题，需要细心维护电梯运行的状态，仔细判断何时上下客。

时间复杂度取决于具体实现。

J 子段和二象性

Idea: 沃若，Solution: _rqy

我们先对构造得到的数组 求前缀和：。则有：

我们把前缀和中的每个元素看成点，大小关系看成边。于是，我们转化题意：一张有向图， 向 和 连边。而数组的最大长度，就是能使这张图不出现环的最大点数。

因此，我们可以从 出发，每次加上 或减去 ，直到回到 。这个过程中经过的编号最大的点的编号减一即为答案。这启发我们贪心地行动：如果当前可以减去 就马上减去 ，否则加上 ，直到回到 为止。

举例说明：如果 ，。则行动路线是 ，答案为 。

至此，只需要打表即可发现答案是 。但依然补充一种证明：

由于经过的编号小于 的点的编号都为 ，可以遍历所有小于 的 的倍数，则这样的最大值为 。这时我们还会加上 ，所以整个过程中的最大值为 ，减一便是答案。

总时间复杂度为 。