Swap and Delete

题目

输入长度为 \(n\) 的二进制字符串，输出执行操作需要的最小成本，使得对于操作之后得到的字符串 \(t\) 的每个字符 \(t_{i}\)，都有 \(t_{i}\neq s_{i}\)，其中 \(1\leq i\leq |t|\)。有两种操作：

• 从字符串 \(s\) 中删除一个字符，操作的成本为 \(1\)。
• 交换字符串 \(s\) 中的两个字符，操作的成本为 \(0\)。

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

思路

由于只有删除操作会导致成本增加，所以我们只需要让字符串 \(t\) 尽可能长就好。首先对字符串 \(s\) 中的 \(0\) 和 \(1\) 计数，然后贪心的构造字符串 \(t\)，如果 \(s_{i}=0\)，则 \(t_{i}=1\)，反之亦然，直到不能增加长度为止。最后最小成本就是 \(n-|t|\)。

Game with Multiset

题目

输入一个整数 \(m\) 表示查询的次数，以及 \(m\) 行查询，每行包含两个整数 \(t_{i}\) 和 \(v_{i}\)。初始时你有一个空的多重集合（multiset）：

• 如果 \(t_{i}=1\)，将元素 \(2^{v}\) 加入集合。（\(0\leq v_{i}\leq 29\)）
• 如果 \(t_{i}=2\)，询问 \(v_{i}\) 是否可以表示为当前集合的某个子集之和，并输出 YES 或 NO。（\(0\leq v_{i}\leq 10^{9}\)）

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

思路

• 方法一：使用数组对 \(t_{i}=1\) 的 \(v_{i}\) 计数，对于每个询问，从低到高遍历 \(v_{i}\) 的二进制 \(1\)。假设当前遍历到 \(2^{k}\)，如果集合中存在 \(2^{k}\) 则当前位可以被表示（假设集合中有 \(c_{k}\) 个 \(2^{k}\)），并且集合中剩余的 \(2^{k}\) 可以合并为 \(\frac{c_{k}-1}{2}\) 个 \(2^{k+1}\)，然后遍历下一位，这样最终可以判断 \(v_{i}\) 是否能被集合表示。
• 方法二：使用数组对 \(t_{i}=1\) 的 \(v_{i}\) 计数，对于每个询问，从高到低遍历 \(v_{i}\) 的二进制 \(1\)。假设当前遍历到 \(2^{k}\)，则执行 \(v_{i}=v_{i}-(\min{(v_{i}>>k,c_{k})}<<k)\) 操作（假设集合中有 \(c_{k}\) 个 \(2^{k}\)），表示将集合中的元素尽可能填补到 \(v_{i}\) 中，最终 \(v_{i}\) 还需要多少值，如果最终 \(v_{i}=0\) 则它可以被集合表示。

Array Collapse

题目

输入长度为 \(n\) 的数组 \(p\)，其中的元素互不相同。输出执行任意次操作能够得到的不同数组个数，结果对 \(998244353\) 取余。每次操作可以选择 \(p\) 的一个子数组（假设为 \([i,j]\)），将子数组中除最小值之外的所有数删除。

数据范围：\(1\leq n\leq 3\cdot 10^{5}\)，\(1\leq p_{i}\leq 10^{9}\)。

思路

• 方法一：使用分治 + 线段树的时间复杂度为 \(O(n\log{n})\) 的思路，比赛时大概就是这个思路，不过想岔了一点。对于区间 \([i,j]\)，使用线段树找到区间最小值的下标，然后左右分治求不同数组的个数，最后将两者相乘。这个方法还有一些特殊情况需要维护，具体看代码。
• 方法二：参考灵神视频单调栈优化 DP，将 \(f[i]\) 定义为以 \(p[i]\) 结尾的子序列个数，然后利用动态规划转移，最后将所有 \(f[i]\) 求和得到答案。单调栈这个规律有点难想，具体看视频吧。

使数组成为等数数组的最小代价

题目

输入长度为 \(n\) 的整数数组 \(a\)，输出执行任意次操作后使得数组中的数全部相等并且是回文数的最小代价（要求该回文数小于 \(10^{9}\)）。每次操作可以将数组中的某个数（假设为 \(a_{i}\)）修改为任意正整数（假设为 \(x\)），对应的代价为 \(|a_{i}-x|\)。

数据范围：\(1\leq n\leq 10^{5}\)，\(1\leq a_{i}\leq10^{9}\)。

思路

如果没有限制是回文数，那么将数组排序之后按如下方式修改，代价是最小的（假设有序数组中的元素为 \(a_{0},a_{1},\dots,a_{n-1}\)）：

• 当 \(n\) 为奇数时，将所有数修改为中位数 \(a_{\lfloor\frac{n}{2}\rfloor}\)。
• 当 \(n\) 为偶数时，将所有数修改为区间 \([a_{\lfloor\frac{n-1}{2}\rfloor},a_{\lfloor\frac{n}{2}\rfloor}]\) 内的某个数。

首先使用反证法证明，最小代价可以通过将所有数修改为数组中的某个数取到。

• 假设将所有数修改为 \(x\)，\(x\) 在区间 \((a_{i},a_{i+1})\) 范围内，其中 \(a_{i}\) 和 \(a_{i+1}\) 表示数组中相邻的两个数。此时 \(x\) 左边有 \(i+1\) 个元素，右边有 \(n-i\) 个元素。将 \(x\) 修改为 \(a_{i+1}\) 会使代价增加 \((i+1)\times (a_{i+1}-x)\)，并且使代价减少 \((n-i)\times(a_{i+1}-x)\)。将 \(x\) 修改为 \(a_{i}\) 会使代价减少 \((i+1)\times (x-a_{i})\)，并且使代价增加 \((n-i)\times(x-a_{i})\)。
• 当 \(i+1<n-i\) 时，将 \(x\) 修改为 \(a_{i+1}\) 会使代价减少；当 \(i+1>n-i\) 时，将 \(x\) 修改为 \(a_{i}\) 会使代价减少；当 \(i+1=n-i\) 时，将 \(x\) 修改为 \(a_{i}\) 或者 \(a_{i+1}\) 代价不变。
• 特别的，\(x\) 在区间 \([1,a_{0})\) 或者 \((a_{n-1},+\infty]\) 范围内时，同理。

然后再使用反证法证明上述结论：

• 假设将数组中的数都修改为 \(a_{i}\) 时，代价最小，\(a_{i}\) 不满足上述条件。
• 当 \(n\) 为奇数时，由于 \(a_{i}\) 不是中位数：
  • 当 \(i<\lfloor\frac{n}{2}\rfloor\) 时，有 \(i+1<n-1-i\)，此时 \(i\) 每向中位数移动一位，代价都会减少 \((n-1-i)-(i+1)>0\)。
  • 反之亦然。
• 当 \(n\) 为偶数时，同理。

综上，得出按照上述方式修改代价最少，即 \(x\) 越靠近中位数代价越小。所以，如果需要将所有数修改为某个回文数，那么该回文数一定是最靠近中位数的回文数。PS：还是灵神的证明更简单。

该题有两种方法可以找到距离 \(x\) 的最近回文数：

• 方法一：将 \(x\) 的前半部分作为回文根，对称之后得到回文数 \(y\)。如果 \(y<x\)，则将回文根加一再做对称得到回文数 \(z\)，然后取 \(y\) 和 \(z\) 中距离最近者；如果 \(y>x\)，则将回文根减一再做对称得到回文数 \(z\)，然后取 \(y\) 和 \(z\) 中距离最近者；否则，\(x\) 本身就是回文数。注意，排除大于等于 \(10^{9}\) 的回文数，以及做加减法时可能会遇到回文根为 \(100\dots0\) 或 \(99\dots9\) 的特殊情况，此时做对称会得到错误答案，我们应该直接根据长度构造回文数。（这个代码还挺好看，把所有情况都直接循环枚举，就可以不用写那么多判断语句）
• 方法二：枚举出 \([1,10^{9}]\) 范围内的所有回文数，然后二分找到距离 \(x\) 最近的回文数。

执行操作使频率分数最大

题目

输入长度为 \(n\) 的整数数组 \(a\) 和一个整数 \(k\)，输出经过至多 \(k\) 次操作之后，数组中众数的最大频率。每次操作可以选择数组中的某个数 \(a_{i}\)，将其增加或者减少 \(1\)。

数据范围：\(1\leq n\leq 10^{5}\)，\(1\leq a_{i}\leq 10^{9}\)，\(0\leq k\leq 10^{14}\)。

思路

排序 + 前缀和 + 滑动窗口。要使众数尽可能多，可以首先对数组排序，假设最终众数有 \(x\) 个，那么这 \(x\) 个数一定是在某个子数组中。使用滑动窗口，将尽可能多的数包含在窗口内，同时满足操作次数小于等于 \(k\)，如果大于 \(k\) 则将左端点右移。类似上一题，将窗口内的所有数都修改为窗口的中位数，所需的操作次数最少。窗口的操作次数可以使用前缀和 \(O(1)\) 的计算出来，假设窗口的左右端点的下标分别为 \(i\) 和 \(j\)，中位数的下标为 \(k\)，则窗口的操作次数为：\((a_{k}\times (k-i)-(s[k]-s[i]))+((s[j+1]-s[k+1])-a_{k}\times (j-k))\)。

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\)。然后使用单调递增栈维护左移的数构成的递增序列，栈中存储数的下标，模拟上述过程并维护最大代价。