BZOJ 4524 [Cqoi2016] 伪光滑数

发布于 2018-02-27  103 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4524

题意:若一个大于 1 的整数 M 的质因数分解有 k 项,其最大的质因子为\(A_k\),并且满足\(A_{k}^{k}\leq n\),\(A_k \leq 127 \),我们就称整数 M 为 N-伪光滑数。现在给出 N,求所有整数中,第 K 大的 N-伪光滑数。


可持久化可并堆练手题。

考虑 DP,\(f_{i,j}\) 表示最大质因子是第 i 个,用了 j 个得到的集合,\(g_{i,j}\) 表示前 i 个质因子用了 j 个得到的集合,即 g 是 f 的“前缀和”。
转移的时候考虑枚举当前质因子用了几个就可以了,发现存在两个操作:集合相加(并),集合乘常数。

对于答案的统计,把每个状态的 max 推入堆里,每次取出堆顶,在相应集合里删掉 max,维护新的 max,迭代 k-1 次,答案即堆顶。

所以对于我们维护的集合,还需要支持查询最大值,发现可持久化可并堆即可。通过左偏树实现了。

 


一个非常弱的准退役OIER