NOIP2023 全题解

最失败的一集。

T1

将每个字符串内部的字符按照大小排序，从小到大和从大到小，然后前后缀维护一下其它串倒序的最小串，与当前串的正序比较一下即可。

T2

先模拟出最后每个 $x’_i$ 与原来 $x_j$ 或 $T,F,U$ 的关系，然后用扩展域并查集判断即可。

T3

个人感觉出的最好的一题，也是最有意思的一道题。

考虑到底要求什么。若 $x_iy_j$ 也可以，但两种情况几乎一样，我们只讨论一种）则称 $x_i$ 与 $y_j$ 匹配，$x_i$ 与 $y_j$ 被覆盖 。问题就相当于，对于每个 $x_i,y_j$，要么被覆盖，要么覆盖所有一部分与之匹配的。问是否存在一种方案，使得所有 $x_i,y_j$ 都被覆盖了。

非常关键的一点是注意到奇怪的特殊性质，并且给了 70pts。不难联想到与正解可能有很大的关联。

考虑特殊性质，容易发现我们可以用 $x_n$ 覆盖 $y$ 一段后缀，或者用 $y_m$ 覆盖 $x$ 的一段后缀。考虑这样的一个算法：从前往后不断尝试用 $y_j$ 覆盖 $x_i$，如果不匹配的话那么将 $i$ 前移直到遇到第一个匹配的为之。这样做是线性的。

再考虑一般情况，很容易想到，将 $x$ 按照最小值 将 $y$ 按照最大值分别分为两部分，前面一段正着做，后面一段倒着做，那么就可以直接套用特殊性质的解法。最终的时间复杂度为 $\mathcal O(nq)$。实际代码比较简洁。

T4

傻逼DP，首先设计出状态 $f(i,j)$ 表示到第 $i$ 天时已经连续打卡了 $j$ 天，这样做前缀 max 一下是 $\mathcal O(n^2)$ 的。尝试优化，但是发现不太方便，于是重新设计状态 $f(i,j)$ 表示 第 $j$ 天到第 $i$ 天连续打卡。这样就很容易用维护区间加，求区间 max 的线段树维护了，时间复杂度 $\mathcal O((n+m)\log n)$。最后离散化一下就可以得到 $\mathcal O(m\log m)$ 的算法。