移除后集合的最多元素数

题目

输入长度为偶数 \(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|)\) 的时间提前预处理出字符数的前缀和。最后，分割数为前缀 + 中间 + 后缀的段数。代码实现时，还有很多其他细节需要注意，强烈建议自己实现一下。

Grouping Increases

题目

输入长度为 \(n\) 的数组 \(a\)，将数组 \(a\) 分割为两个子序列（可能为空），输出两个子序列中满足 \(b_{i}<b_{i+1}\) 的下标 \(i\) 的数量之和的最小值。

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

思路

贪心。假设将数组 \(a\) 分割为数组 \(b\) 和 \(c\)，从空数组开始，将 \(a\) 中的元素添加到 \(b\) 或 \(c\)。假设 \(b\) 和 \(c\) 的最后一个元素分别为 \(x\) 和 \(y\)（\(x\leq y\)），如果 \(a_{i}\leq x\) 或 \(a_{i}>y\)，则将 \(a_{i}\) 添加到 \(b\)，否则添加到 \(c\)。

Non-Decreasing Colorful Path

题目

输入有 \(n\) 个顶点和 \(m\) 条边的连通的无向图（没有重边和自环），每个顶点上有一个整数 \(A_{i}\)，输出所有从顶点 \(1\) 到 \(N\) 的简单路径的最高得分。如果路径中顶点上的整数构成的序列非递减，那么该路径的得分为序列中不同整数的个数，否则得分为 \(0\)。

数据范围：\(2\leq n\leq 2 \times 10^{5}\)，\(1\leq A_{i}\leq 2\times 10^{5}\)。

思路

虽然是无向图，但是序列需要非递减才能有得分。进一步观察可以发现，对于一条非递减路径，所有包含相同整数的顶点只会贡献 \(1\) 个得分，我们可以将这些顶点缩为一个顶点。所以，只需要建立满足递增条件的有向边，如果边的两个顶点包含相同的整数，则使用并查集将它们连接（缩点）。然后问题就变为求 DAG 中两个顶点之间的最长路径，不过和一般的使用拓扑排序 + 动态规划来求解的方式不同，因为缩点的缘故，该题不是很好使用拓扑排序。由于 \(A_{i}\) 的范围比较小，从小到大枚举顶点整数，然后扩展以该整数为起点的边，结合动态规划可以比较方便的求出答案。实现时，需要注意起点和终点同样可能被缩点，使用时将其替换为并查集中所在连通块的根节点。