• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

2021-09-12算法周记——根号分治2

开发技术 开发技术 3小时前 2次浏览

本周小结

本周并未学习什么算法,而是再深入了解了根号分治,复习了一点数据结构。
开学第二周,制定了读书计划与刷题计划。

根号分治2

按照老师的话,“小的东西种类不多,大的东西倍数不多”。根号分治不仅可以用来解决一些数据结构题,还可以用于复杂度的分析(空间与时间都可以)。比如熟知的“数论分块”的时间复杂度便是如此。
也有一些非经典的数据结构题可以使用根号分治,根号划分的内容不再是询问,而是一种“二级数据”。
一道题目:自然数拆分

传统解法

看成完全背包,解题。
另一种思路:定义状态(f(i,j)):将(i)分成(j)个数的方案数。
此时的决策十分奇怪,有两种决策,为:
①加入一个(1),即从(f(i-1,j-1))转移
②将已有的所有数(+1),即从(f(i-j,j))转移
(j)应该放于外层循环,可惜时间复杂度还是(O(n^2))

小东西

直接计算(leq L)的完全背包,记为(g[])

大东西

只需要定义状态(H(i,j)):将(i)分成(j)个数,这(j)个数都大于等于(L+1)的方案数。
(h[i])(i)分成若干个不小于(L+1)的数的方案数。

答案

(ans=sum_{i=0}^n{g[i]*h[n-i]}%p)

Floyd判圈算法

2021-09-12算法周记——根号分治2
没啥好记录的,很简单。


程序员灯塔
转载请注明原文链接:2021-09-12算法周记——根号分治2
喜欢 (0)