第 379 场力扣周赛

移除后集合的最多元素数

题目

输入长度为偶数 \(n\) 的数组 \(a\) 和 \(b\)，输出从 \(a\) 和 \(b\) 中分别选择一半元素构成的集合的最大大小。

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

思路

要使集合尽可能大，肯定优先选择除 \(a\) 和 \(b\) 交集以外的元素，假设分别为 \(x\) 和 \(y\)，则可以选择 \(s=\min(x,\frac{n}{2})+\min(y,\frac{n}{2})\) 个不同元素。此时还有 \(n-s\) 个元素待选，假设交集的大小为 \(z\)，则答案为 \(s+\min(n-s,z)\)。

执行操作后的最大分割数量

题目

输入长度为 \(n\) 的字符串 \(s\) 和一个整数 \(k\)，输出至多改变一个字符时，执行操作能够得到的最大分割数。每次操作可以分割 \(s\) 的最多包含 \(k\) 个不同字符的最长前缀。

数据范围：\(1\leq n\leq 10^{4}\)，\(1\leq k\leq 26\)。

思路

首先，很容易想到暴力做法，枚举每个位置的所有改变情况，然后通过遍历求分割数，时间复杂度为 \(O(n^{2}|\Sigma|\log{|\Sigma|})\)。显然，可以优化的部分就是最后遍历求分割数的 \(O(n\log{|\Sigma|})\)。然后观察修改字符相比不修改字符会产生什么变化，可以发现修改字符所在的分割段的长度可能发生变化，而前缀的分割数是固定的。可以想到预处理原字符串每个位置 \(i\) 的后缀分割数，问题就剩下如何快速求得修改字符所在段的右端点。由于字符数随着长度的增加而增加，所以可以通过二分求得该段的右端点，这还需要花费 \(O(n|\Sigma|)\) 的时间提前预处理出字符数的前缀和。最后，分割数为前缀 + 中间 + 后缀的段数。代码实现时，还有很多其他细节需要注意，强烈建议自己实现一下。