BZOJ 4524 [Cqoi2016] 伪光滑数


题目链接: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 次,答案即堆顶。

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

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 4524 [Cqoi2016] 伪光滑数


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,