题目
输入长度为 \(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\)。
题目
输入有 \(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}\) 的范围比较小，从小到大枚举顶点整数，然后扩展以该整数为起点的边，结合动态规划可以比较方便的求出答案。实现时，需要注意起点和终点同样可能被缩点，使用时将其替换为并查集中所在连通块的根节点。
题目
输入长度为 \(n\) 的由小写字母组成的字符串 \(s\)。如果一个字符串仅由单一字符组成，则它被称为特殊字符串。输出在 \(s\) 中出现至少三次的最长特殊非空子字符串的长度，如果不存在则输出 \(-1\)。
数据范围：\(3\leq n\leq 5\times 10^{5}\)。
思路
可以直接想到二分答案，时间复杂度为 \(O(n\log{n})\)。不过该题有 \(O(n)\) 的做法，其实就是分类讨论。首先遍历一边数组，将数组按照字母分段，把对应的长度存到桶中。假设字符串 \(s\) 的最长特殊子字符串的长度为 \(m\)，则答案必定在 \([m-2,m]\) 范围内，枚举答案然后判断是否满足条件即可。当然还可以像灵神一样讨论得更细，但是不好理解。
题目
输入长度为偶数 \(n\) 的字符串 \(s\)，以及长度为 \(m\) 的二维数组 \(q\)，其中 \(q_{i}=[a_{i},b_{i},c_{i},d_{i}]\)。对于每个查询 \(i\)，可以将区间 \([a_{i},b_{i}]\) 和 \([c_{i},d_{i}]\) 中的字符重新排列，输出是否能让字符串 \(s\) 变为回文串。每个查询是独立的。
数据范围：\(2\leq n\leq 10^{5}\)，\(1\leq m\leq 10^{5}\)，\(0\leq a_{i}\leq b_{i}<\frac{n}{2}\)，\(\frac{n}{2}\leq c_{i}\leq d_{i}<n\)。
思路
比赛时基本的思路是有的，就是没有实现出来。首先可以将后半段字符串反转，将原串当成两个字符串，这就将问题转化为判断操作之后两个字符串能否相等，从而简化实现。然后就是预处理前缀的字符计数（类似前缀和），最后对每个查询分类讨论，两个区间是相离、相交还是包含关系。个人觉得稍微复杂点的就是相交关系该如何判断，具体可以看题解区。