CUTE 和 ETUC

f[i][j][k] 表示考察到第 i 个字符，cute 匹配状况到第 j 个字符，etuc 匹配到第 k 个字符时，最多有多少个 cute + etuc，最终答案为 f[n][0][0]。 复杂度 O(n)。

Ximpha 的仁慈

将两个序列想象成折线，则这两个折线一定在某处相交（可能在 0 处或 n + 1 处），枚举相交位置和相交的值。 则问题变为在以某个位置，某个值结尾时，最长上升和下降子序列长度和为多少，这两个序列天然不会有重复。 复杂度 O(n^2)。 这个题 n 更大的版本只需要考察如何快速计算而不枚举相交的值即可。

Nero 的魔法

对于一个排列，考虑将数字从大到小插入进去，则容易发现，除了最大值（最大值不贡献区间个数）以外，每次插入“美”的区间个数要么多2，要么多1（此时该数字前方或后方没有数字）。 所以这问题变为除了最大值之外，恰有 2n - 2 - m 个数字，前方或后方没有一个数字比它大的。 以最大值的位置将排列劈开，每个数字管其往后（前）到第一个比它大的数字之前的的所有数字，则这个划分为第二类斯特林数的划分类别，容易发现该问题答案为： stirling[n - 1][2n - 2 - m] * 2 ^{2n - 2 - m}。 其中 stirling[i][j] 为第二类斯特林数。 复杂度 O(n^2) 。

超级可爱链

注意到 x^2 + y^2 + xy 是一个凸函数。考察第 i 类祭坛，和第 j 类祭坛，则答案一定在所有点两两做差的点构成的凸包上。 于是按照类别分治后，利用 minkowski 和求得所需要的凸包即可。 注意到求凸包时所需要的顺序可以预先排好，之后分裂再归并即可保持顺序。 复杂度 O(nlogn) 。