线性递推小结 作者: laok 时间: 2019-10-13 分类: 算法小结 评论 问题给定$n,k,f_0\dots f_{k-1},a_1\dots a_{k}$,定义$f_n=\sum_{i=1}^k f_{n-i}a_i$,求$f_n$。- 阅读剩余部分 -
子集卷积 作者: laok 时间: 2019-09-24 分类: 算法小结 评论 子集卷积是这样的问题:$$f_S=\sum_{T\subset S} g_Th_{S-T}$$给定$g,h$求$f$。- 阅读剩余部分 -
[学习笔记]尺取法维护不支持删除的信息 作者: laok 时间: 2019-09-13 分类: 算法小结 评论 上午模拟赛考了这个trick,然后我不会,学会了来写一波博客。考虑一类求最短区间的问题,满足单调性(可以two-pointers),插入很快,但是删除很慢,不过可以快速的判断两段的信息合并能否满足条件。这时普通的尺取法就没法用了。怎么解决呢?- 阅读剩余部分 -