最近莫名其妙的做了许多矩阵优化DP的题。。。在这里做一下总结。。。
矩阵优化dp，是将dp的状态化为矩阵，dp的转移也化为矩阵，将转移变为矩阵乘法的过程。
1.什么样的题可以用矩阵优化？
目前发现两类：
第一类：
线性常系数递推方程，就是像斐波那契数列那样的（f[i]=f[i-1]+f[i-2])
对于这样的题，我们需要构造2个矩阵，初始矩阵，转移矩阵。
初始矩阵我们一般认为是列向量，转移矩阵一般为一个N*N的方阵。
READ MORE →
【高级数据结构】Splay整理
Yts教授喜欢数据结构，他教了我们许多高级数据结构。
这一天Yts教授看到了萌萌的icebound同学，于是就找到icebound同学，教会了他splay。。。。
在算法竞赛里常用的平衡树只有splay和treap，然而treap由于std::set的原因，鸡肋了许多。
Splay的高明之处在于，Splay有一个神奇的操作：换根。
READ MORE →
关于括号序列的那些事
关于括号序列，有很多有意思的题可以说。最近我就做了许多关于括号序列的题，其中有很简单的，也有很难的。
这篇文章用于记录关于括号序列的一些结论和趣题，不定期更新。
READ MORE →
选修课【丢人】小文章
HBCPC2018题解
以下是由icebound和phx写的hbcpc2018题解，有可能有错误。。
更新：标程已经上传，请访问：HBCPC2018标程
wordpress对markdown和latex支持有点差，不但把自适应给搞崩了，还出了各种bug，这里给出pdf下载地址(度娘网盘)。
链接：https://pan.baidu.com/s/18UgFvEYeAOY4dJoujFOy-w
密码：2zml
以下是正文：
READ MORE →