题解：P10785 [NOI2024] 集合

ty_mxzhn · 2024-07-23 12:26:50 · 题解

免责声明：场外选手纯凑热闹。我只是一个 CSP-S 2= 的准退役选手别骂我呜呜呜

注：本题解中哈希是广义的，把一些信息压缩或转化成另一些信息的方式。

看到排列对应，想起自己之前做过的一道题。在看到判定相等，就发现本题可能可以使用哈希解决。2022 年也考了。

作为一道哈希题，第一步肯定需要思考一种可能的哈希方案。容易想到记 S_{x} 为颜色 x 在集合出现时集合的编号所构成的集合。例如：a_1=\{1,2,3\},a_2=\{2,1,4\},a_3=\{1,3,4\} 中，S_1=\{1,2,3\},S_2=\{1,2\}。再记多重集合 H 为所有颜色的 S_x 构成的集合。通过手玩发现 a \cong b \Leftrightarrow H_a =H_b。

众所周知的，判定两个集合相等可以使用哈希。容易想到，\displaystyle \prod_{i=1}^m G(\sum_{j=1}^n [i \in S_j] \times p^j) \bmod p_0 是一种非常优秀的哈希方式。其中 G 是一个你自己任选的哈希函数。

其实做到这一步已经有可能可以实现了。但是注意到题目中并不需要你对任意的两个数组哈希，而是 a[l,r] 和 b[l,r]。这意味着判定具有单调性。我们可以移动 r 然后找最小的 l 满足 [l,r] 被判定为 \texttt{Yes}。（双指针）

双指针时哈希值可以支持删除和插入。于是这道题就做完了。

总结：哈希和双指针两个关键点挺难想的。个人感觉板回了去年 NOI 2023 Day1 T1 方格染色较水的局面。

但是作者太菜了，而且怕给其他人带来不便，所以不放代码了。