P8330 [ZJOI2022] 众数 题解

文章P8330 [ZJOI2022] 众数 题解分享给大家，欢迎收藏极客资料网，专注分享技术知识

算法一

枚举所有区间，用 bitset 维护可以做到 \(O(\frac{n^3}{w})\) ,实际上 \(O(n^3)\) 可过，然而我并没有写这个算法，因为算法二更好写，而且时间复杂度可以过。

预计得分:20pts.

实际得分:20pts.

算法二

离散化之后枚举原来的值和更改后的值，将所有这些值记下来，原来值设为 \(-1\)，更改后设为 \(1\)，取一个最大的区间即可。

令值的数量为 \(m\)，\(cnt_i\) 表示值为 \(i\) 的数的数量。

时间复杂度为 \(O(\sum_{i} \sum_{j,i\neq j} cnt_i+cnt_j) = O(nm)\) 。

完全优于算法一。

预计得分:40pts.

实际得分:40pts.

算法三

这里（可能）显然会用到根号分治。

如果出现次数大于 \(B\) 的，用算法二即可。

如果出现次数小于 \(B\) 的，记 \(g_{i,j}\) 表示 \(g_{i,j}\) 是最小的使得 \([i,g_{i,j}]\) 这个区间里的众数出现次数为 \(j\) 的，这里 \(j<B\) ，只考虑 \(cnt_i<B\)。

这个预处理是简单的。

枚举 \(i,j\) 表示更改区间开始的点和这个更改区间的众数的出现次数，这些众数都更改为 \(a_{i-1}\)。

这样的时间复杂度可以控制在 \(O(nB)\)

最后的时间复杂度为 \(O(\frac{n^2}{B} + nB) = O(n\sqrt n)\)

预计得分:100pts.

实际得分:100pts.

文章来源:https://www.cnblogs.com/hnczy/p/20035826
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！