NOIp2023 题解

bunH2O · 2023-12-08 23:49:23 · 个人记录

之前写了一篇21年省选的题解，感觉观感还可以。本来说再写一篇往年省选的，但是省选好难，一道不会。

但题解还是要接着写的，所以今天就偷懒写点这个。

T1：按照从小到大/从大到小的方式对每一个数组内部排序，然后只需对每个字符串判断其从小到大序是否比其他的从大到小序要小即可。注意特判 n=1。

T2：用数组维护操作，随后把每个位置看作一个关系，进而将每个位置视作点，关系视为边建图。判断其是否有U/是二分图即可。

T3：先考虑暴力。考虑 f_{i,j} 当前在 X 的第 i 位和 Y 的第 j 位。转移 f_{i,j}=f_{i-1,j}~|~f_{i,j-1}~|~f_{i-1,j-1}。所以可以将其抽象成一个网格图，有一个特殊性质就是每行、每列之间呈包含关系。因此可以看出 f_{i-1,j-1} 的转移是无用的。先考虑特殊性质，我们考虑除最后一行外点数最多的一行，若其点数不为 m 则比有一列全空，列的情况同理。而若有一行一列全空则必然无解，否则必有一行/一列全满。所以问题等价于从原点走到该行/列，可以递归进行求解。下面是正解：依然考虑最多的一行和一列，若有一列不全满则无解，虽然转化为两个特殊性质（从原点开始的和从末点开始的倒着的）。

T4：考虑暴力，令 f_i 表示第 i 天跑步下的最优解。不难发现可以线段树优化。不难发现可以离散化。然后就做完了。

啊，好累，摸了。