UOJ Logo Magolor的博客

博客

从高斯消元到"QGXZ分解"

2019-10-24 15:53:06 By Magolor

震惊!$0\%$的人都不知道,高斯消元还可以这样做……

继去年为大家带来树状数组黑科技讲义,之前为大家带来求后缀数组的SAM与SA-IS方法以及Ukkonen算法与后缀树构造后缀数组之后,今年带来全新的: 高斯消元讲义!

本文将简单介绍矩阵利用高斯消元完成的各种操作和科技,并用C++不使用任何第三方库手写一个封装有矩阵类型和多种操作的库

主要内容包括: 矩阵的基本运算,矩阵的转置(transpose),高斯消元,矩阵的echelon form和reduced echelon form,矩阵的迹(trace),矩阵的秩(rank),矩阵的逆(inverse),矩阵的行列式(determinant),高斯消元解线性方程组,线性方程组的通解,LU分解,PLU分解,以及由于我孤陋寡闻并没有查到的、大佬 @GXZlegend 传授的”GXZ分解”和”QGXZ分解”。然而本文矩阵都是double写的似乎OI中用的比较少。

详细内容欢迎大家访问我的博客: 从高斯消元到"QGXZ分解"

Ukkonen算法与后缀树构造后缀数组

2019-08-18 23:26:24 By Magolor

为什么要学习Ukkonen算法?



被大佬们diss了......所以......

本文介绍了Ukkonen算法构造后缀树、如何用后缀数组构造后缀数组从而得到一个$O(n)$构造后缀数组的算法(不考虑字符集大小),并与其他优秀的后缀数组算法进行了速度比较。

食用本文前建议对后缀数组(SA)和后缀树(ST)有基本了解。

详细内容欢迎大家访问我的博客: Ukkonen算法与后缀树构造后缀数组



感谢各位大佬,不然我是不会去学习Ukkonen算法的。


当我学完Ukkonen算法,我果然被它惊异到了,不得不要感叹一句:


所以Ukkonen方法果然是又慢又复杂。

所以Ukkonen方法果然是又慢又复杂。

所以Ukkonen方法果然是又慢又复杂。

求后缀数组的SAM与SA-IS方法

2019-08-13 17:13:25 By Magolor

震惊!$0\%$的人都不知道,后缀数组还可以这样求……

继去年为大家带来树状数组黑科技讲义之后,今年带来全新的后缀数组黑科技讲义!

众所周知后缀数组有$O(n \log n)$的倍增方法以及$O(n)$的DC3方法。而本文将会简单介绍倍增方法并详细讲解黑科技: $O(n)$的SAM方法以及SA-IS方法。

食用本文前建议对后缀数组(SA)和后缀自动机(SAM)有基本了解。

详细内容欢迎大家访问我的博客: 求后缀数组的SAM与SA-IS方法

已更新Ukkonen算法: Ukkonen算法与后缀树构造后缀数组

安利一份树状数组黑科技讲义

2018-08-27 18:37:45 By Magolor

震惊!$99\%$的人都不知道,树状数组还有这些功能……

本文中,简单介绍了: 树状数组的基本使用方法,下标平移和反转技巧,清零技巧,维护前后缀最值,二维树状数组,树状数组与差分的结合(包括区间加单点查询以及区间加区间查询),树状数组上二分,树状数组代替简单线段树。没有探讨并简单探讨了关于树状数组进一步代替线段树和树状数组可持久化的问题,给读者留下了思考空间

详细内容欢迎大家访问我的博客: 树状数组黑科技讲义

共 4 篇博客