Codeforces Round 915 (Div. 2)

Begginer’s Zelda

题目

输入一颗树，输出执行的最少操作次数，使得该树只有一个节点。每次操作可以选择树中的两个节点，将它们之间的路径压缩为一个节点，所有连接路径上节点的边都会连向新节点。

数据范围：\(2\leq n\leq 10^{5}\)，\(1\leq u_{i},v_{i}\leq n\)，\(u_{i}\neq v_{i}\)。

思路

每次操作贪心的选择两个叶子节点（度数为 \(1\) 的节点都看作叶子），根据叶子节点的数量 \(x\) 的奇偶性分类讨论：

• 如果 \(x\) 为奇数，\(x=1\) 需要 \(0\) 次操作，\(x=3\) 需要 \(2\) 次操作，之后每增加两个叶子，都会使操作次数加 \(1\)，由于数据范围限制初始时叶子至少有 \(2\) 个，所以操作次数为 \(\frac{x+1}{2}\)。
• 如果 \(x\) 为偶数，\(x=2\) 需要 \(1\) 次操作，\(x=4\) 需要 \(2\) 次操作，之后每增加两个叶子，都会使操作次数加 \(1\)，所以操作次数为 \(\frac{x}{2}\)。
• 最后，可以将两种情况的公式合并为 \(\lfloor\frac{x+1}{2}\rfloor\)。

Largest Subsequence

题目

输入长度为 \(n\) 的字符串 \(s\)，输出执行的最少操作次数，使得字符串有序。每次操作可以将字符串中字典序最大的子序列循环右移一位。

数据范围：\(1\leq n\leq 2\cdot 10^{5}\)。

思路

首先使用单调栈求出字典序最大的子序列（非严格单调递减），然后通过观察可以发现，执行多次操作最终会将该子序列反转。相当于求最少右移次数，使得子序列反转，该次数等于子序列长度减去子序列中最大字符的数量。其次，还需要判断子序列反转之后，字符串是否有序。

Cyclic MEX

题目

输入一个包含 \({0,1,2,\dots,n-1}\) 的排列 \(p\)，输出排列 \(p\) 的所有循环移动的最大代价。对于数组 \(a\)，它的代价为 \(\sum_{i=1}^{n}{\operatorname{mex}([a_{1},a_{2},\dots,a_{i}])}\)。

数据范围：\(1\leq n\leq 10^{5}\)。

思路

观察每循环左移一次，代价是如何变化的：

排列 \(2,3,6,7,0,1,4,5\) 对应的代价为 \(0,0,0,0,1,4,5,8\)；

排列 \(3,6,7,0,1,4,5,2\) 对应的代价为 \(0,0,0,1,2,2,2,8\)；

排列 \(6,7,0,1,4,5,2,3\) 对应的代价为 \(0,0,1,2,2,2,3,8\)。

可以发现每当将数 \(x\) 移动到排列末尾，所有大于 \(x\) 的 \(\operatorname{mex}\) 值都会变为 \(x\)，然后 \(x\) 位置对应的 \(\operatorname{mex}\) 值为 \(n\)。

我们可以首先将排列移动为 \(1,4,5,2,3,6,7,0\) 形式，对应的代价为 \(0,0,0,0,0,0,0,8\)。然后使用单调递增栈维护左移的数构成的递增序列，栈中存储数的下标，模拟上述过程并维护最大代价。