P9572 题解

· · 题解

第一次打基础赛，感觉不错。

个人感觉难度作为 T4 来讲不大，本人花了 8 min 不到 AC。

而且值域 10^6 感觉有点提示做法的感觉，真的不考虑开大值域加个离散化吗。补充：出题人在讨论区说了离散化超纲，不过还是说说离散化做法。

首先 S^k 是 k 个 S 拼接而成，所以贪心考虑，先不想最小 k 的事情，至少说我们拼 m 个 S 必定是可以的，而第一问的答案就是 T 数组中在 S 数组里的数的个数。

接下来继续考虑 k 最小是多少。

继续贪心，开两个变量，nwk 代表现在已经拼接了的次数，和 nwi 代表现在的坐标。

对于每一个 T 中的元素，如果在 S 里出现，那么找到 nwi 之后的第一个这个元素的位置，并把 nwi 改成这个位置，如果找不到，代表这个元素在其前面，我们将 nwk 增加，再将 nwi 变成这个元素在 S 里第一次出现的位置即可。最后的 nwk 就是答案。

问题来了？如何维护某个数在某个位置之后第一次出现的位置？

可以提前预处理，复杂度 O(nV)（V 是 \max{(\max^{i=n}_{i=1}S_i,\max^{i=m}_{i=1}T_i)}），可以拿到 V 很小的 20 分。

不过看起来...某个位置之后第一个，这不是很像二分吗？

考虑用邻接表记录每一种元素在 S 中出现的所有位置，查询时二分即可。

预处理是 O(n)，每次查询复杂度 O(\log n)，整体时间复杂度 O(n+m \log n)，空间复杂度 O(n+V)。

如果将 V 增大到 10^{18} 怎么办？内存会炸掉的）

考虑离散化，因为答案还有计算步骤与具体大小无影响，所以只要相同的数离散成相同的数，不同的数离散成不同的数即可。（事实上离散化是超纲内容）

最终时间复杂度 $O(n \log n + m\log n)$，空间复杂度 $O(n)$。