NOI 2023 简易题解

· · 个人记录

P9478 [NOI2023] 方格染色

离散化成左开右闭，使用扫描线与线段树或树状数组计算横竖线的并后，暴力枚举斜线与其他线，用 map 去重交点计算并。

时间复杂度 O(n\log n)。

P9479 [NOI2023] 桂花树

注意到第一个条件等价于 [1,n] 的点构成的虚树为 T，第二个条件等价于 [1,i] 的点构成的虚树上的点必须在 [1,i+k] 以内。

设 dp_{i,s} 表示前 i 个点构成的虚树包含了 [1,i] 与 i+u[u \in s] 这些点。每次加入 i+1，如果不在虚树上的话有两种情况，第一种情况是加入到一条边上，第二种情况是加入到某个点儿子集合里。第一种情况是可以随便加的，因为加入之后不会有任何两个其他点的 lca 为它。第二种情况则需要讨论父亲是否已经在虚树内，如果不在的话则要从 [i+1,i+k+1] 中选一个点加入到某一条边上后再加入当前点。

直接 dp 复杂度 O(Tm2^kk)，可以通过。

P9480 [NOI2023] 深搜

咕。

P9481 [NOI2023] 贸易

最短路可以拆成 u\rightarrow lca\rightarrow v。

用 dijk 处理出每个点它的任意一个祖先到它的距离后统计答案。

时间复杂度 O(2^nn^2)。

P9482 [NOI2023] 字符串

我们把每个前缀与后缀排序，发现相当于算一个区间内的前缀字典序大于当前后缀的前缀个数再减去不能在当前区间里分出胜负的字典序大于当前后缀的前缀个数。

后者的出现代表着偶回文串的出现，分析一下字典序关系大小的本质是第一个不一样的字符比较大小，所以我们只需要对最多 n 个满足左边字符大于右边字符的极长偶回文串计算即可。

所以整个题可以用 SA+树状数组 在 O(n\log n) 的时间复杂度完成。

P9483 [NOI2023] 合并书本

该做法来自 @zhoukangyang

建出操作树，按照子树重量和进行链剖分，观察到重量大的一定深度也大，否则可以调整使得答案不劣。接着我们发现可以将链缩成点，因为记录链上合并子树的顺序是不必要的。

接下来新树能对应一棵原树的条件是一个 deg 为 i 的点的儿子中，必须满足对于所有 j\leq i-1 都有 \sum_u [\deg_u\leq j]\geq j

考虑从上往下一层层做，我们显然只关心每层的 deg 集合。感受一下，先钦定一下每儿子度数都取到上界，然后我们每次选度数最大的点将其度数减 1，最优秀的方法一定在进行若干次之后取到。

然后直接搜就行了。