军训终于结束了呀QwQ(翘了两个星期的网络赛(逃))，在程序设计课上刷学校OJ的时候，发现世界上居然还有BFPRT这种神仙算法。什么你也没听过？没事下面我们就通过一道例题来一步一步了解神奇的BFPRT算法。 思考一下 如果给定一个n个数的数组，要你输出数组中第k大数，该怎么做？这时你也许会振臂高呼：“水题！”的确，在n不太大的时候，是有很多方法的，比如： 1.将n个数排序(比如快速排序...
在最近的训练中，遇到了很多与LCA有关的算法。今天就让我们一起来重温一下求解LCA的三种主流算法吧！ LCA简介 在求解LCA之前，我们需要先知道什么叫LCA。LCA（Least Common Ancestors），即最近公共祖先，是指在有根树或者DAG中，某两个结点u和v最近的公共祖先。 觉得很迷？没问题，下面我们来通过一个例子来理解一下LCA的内涵，我们首先有一颗可爱的树(特别感谢大...
最近刚刚打完ACM的校队选拔赛，最后幸运女神眷顾，压线进了校队[做梦笑醒的说]。在这段时间的集训中，新学习了很多很有意思的算法，今天就让我们一起来学习回文串题目的大杀器——回文树吧！ 思考一下 现在我们提出一个问题： 假如给你一个长度为 n 的字符串 S （n≤1e5），需要你求解本质不同的回文串的数量及各自的出现次数是多少（不包括空串）。[本质不同的字符串通俗来说就是长的不一样的字符串...
这几天刚刚重拾打程序的激情，还有些生疏啊……拜读了大佬的Blog后，突然想码一篇模拟退火。今天就让我们一同从爬山算法到模拟退火，走进神奇的玄学算法。 爬山算法 算法简介 爬山算法是local search(局部搜索)算法中最简单的一种。当我们遇到的问题的解空间很大时，我们想从中直接获取最优解是很耗时间的。但是，我们可以做到的是，我们可以从一个小的解空间短时间获得最优解，这就是local ...
由于准备高考的缘故大半年没更新了呀……最近搞完自主招生终于可以慢慢补档了。最近通过大佬的BLOG初略地复习了一下这两种排序。今天，就让我们一同从桶排序到基数排序，走进神奇的排序算法吧！ 初级-桶排序 一说到排序算法，可能不少同学都会第一时间喊出"我大快排天下第一！"其实不然。我们知道快排这种基于比价的排序算法时间复杂度下限是 O(n log n) 。至于为什么，我们可...