CF2031

A

题意

给一个单调不增序列，每次操作可以单点修，问把序列变为单调不减序列需要的最小操作次数。

分析

注意到事实上我们需要修改的数字非常多。考虑一个中间点 \(x\)，我们将所有小于 \(x\) 的数提升至 \(x\)，所有大于 \(x\) 的数减少至 \(x\)。模拟这个过程是 \(O(n^2)\) 的，但我们发现这么做的答案就是 \(n-cnt_x\)，那用全体减掉众数的出现次数就是最终答案了。

B

题意

给一个排列，每次操作可以交换相邻且相差为 \(1\) 的两个数，问通过这样的交换是否可以将这个排列排序为递增。

分析

一个关键性质是任何数不会被交换两次，这表明模拟这个过程的复杂度是线性的，那就按照题意模拟就行了。

如果两个数满足相差为 \(1\) 且前面的数不在它应该在的位置上我们就选择交换，扫一遍后检查数组是否已经排序。

C

题意

构造一个长度为 \(n\) 的序列，满足：

• 任意元素至少出现两次；
• 同种元素的距离为完全平方数；
• 最大元素不超过 \(10^6\)。

分析

\(n\) 为偶数的情况是平凡的，只需要每个数重复两遍就行。

考虑奇数的情况，发现我们不得不至少将一个数重复三遍，设三个出现的位置按顺序分别为 \(x,y,z\)，令 \(a^2=d_1=y-x,b^2=d_2=z-y,c^2=d_3=z-x\)，则有：

这是一个勾股定理的形式，不难发现最小的解为 \(a=3,b=4,c=5\)。那么 \(d_1=9,d_2=16,d_3=25\)。可以在第 \(1,10,26\) 的位置上放 \(1\)，其他位置以成对凑为主体，第二段奇数的空就让 \(12\) 空开一个间隔为 \(4\) 的空就行了。

无解的情况即对应奇数且 \(n \le 26\)。

D

题意

给一个序列，兔子向更大的下标跳只能跳到更矮的位置，向更小的下标跳只能跳到更高的位置，问从每个 \(i \in [1,n]\)，从 \(i\) 出发能跳到的最高的位置。

分析

首先答案的下界是前缀最大值。

考虑一个跳的策略：先向大下标跳到一个很矮的位置，再向小下标跳到一个很高的位置。这个过程可以重复以到达较靠后的位置。注意到这实际表明了前面的高的位置可以继承后面的矮的位置的答案，这启发我们倒着扫。

我们先把答案置为前缀最大值，然后从后往前扫，每个位置继承后面比自己矮的位置的答案，用单点修前缀 max 的 BIT 可以维护。

E

题意

假设初始有一棵根为 \(1\) 的满二叉树，定义一次删除操作为：

• 选择一条树边 \((u,v)\)，不妨令 \(u\) 为父亲；
• 将所有 \(v\) 的儿子与 \(u\) 相连；
• 删除节点 \(v\)。

现在给定一棵已经被进行了一系列删除操作的树，问最少需要高度为多少的满二叉树才能通过若干次删除操作将满二叉树变为给定的树。

分析

从满二叉树开始考虑较为困难，我们可以从给定的数开始考虑如何还原回满二叉树。

注意到一个节点的儿子数量不大于 \(2\) 是容易处理的，因为删除一个叶子不影响其他节点。

现在我们考虑儿子数量为 \(3\) 的情况，发现可以选取其中两个儿子新建一个父亲，另一个节点直接连接到父亲。贪心地，我们会选择两个高度较小的儿子。

数量为 \(4\) 呢？一种自然的思路是两两分组合并，但稍加思考就会发现这并不一定最优，因为可能有一个儿子非常高，这时把这个儿子直接连接父亲，剩余三个按照上面的方法合并即可。

这表明儿子的合并不能简单贪心，我们转而在每个节点上开一个优先队列，每次将两个高度最小的节点合并，当剩余的节点只有两个时直接与父亲相连。