祝馀宫

算法简介：同袍的义理拉格朗日插值法，是一种已知多项式函数 $f(x)$ 上的 $k$ 个点 $(x_i,y_i)$ 求这个多项式的系数的东西。是以法国十八世纪数学家约瑟夫·拉格朗日命名的一种多项式插值方法。 算法演示：僚佐的才巧算法推导 ：御敌的执定多项式的系数表示法众所周知一个 $k$ 次多项式可以被它的 $k+1$ 个系数唯一地确定，即： f(x) = \sum\limits_{i = 0}^{k}a_ix^i这种确定多项式的方法叫做多项式的系数表示法。 多项式的点值表示法众所周知，一个 $k$ 次多项式同样的可以被图上的 $k+1$ 个点唯一确定。我们设这个多项式的形式为： f(x) = \sum\limits_{i = 0}^k a_ix^i那么我们把这几个点带入到这个式子里，就可以得到 $k+1$ 个 $k+1$ 元一次方程组（小学生都知道吧） \begin{cases} a_0+a_1x_1+a_2{x_1}^2+\dots+a_k{x_1}^{k}=y_1\\ a_0+a_1x_2+a_2{x_2}^2+\dots+a_k{x_2}^{k}=y_2\\ \dots\ ...

算法简介：乌眼Boruvka 算法是一个不常用的计算最小生成树的算法，通过不断地合并一个一个的连通块使用贪心的思想在 log 的复杂度求出结果。 算法演示：鸦羽算法流程：心魔我们首先想到，对于点 u 和 v ，如果 v 是点 u 所有边中距离最短的点，那么这条边一定在最小生成树中。 那么不难做出第一步：把最短的边连起来，这样子就会把他们变成很多个连通块。这样的连通块最多有 n 个。 接下来，我们把每一个连通块都看成一个点，那么继续找出最短的那条边一直重复，这样的当我们把所有的连通块都变成一个连通块的时候，就得到了最优解。 每一次至少变成原来的二分之一，复杂度就是 $O(n+\cfrac n 2 + \cfrac n 4 + …)$ 也就是 $O(m\log n)$ 其中 m 是边的数量 算法例题：彻证大秦为你打开题目传送门 这道题目的话，是一个完全图，完全图的特点就在于边特别多，像 kruskal 算法这种按照边作为复杂度的东西，显而易见就是会超时的，所以说这是候我们的 boruvka 就上场了。我们发现这种位运算的操作可以通过一些数据结构维护，但是这样的操作过程似乎不可以用 kru ...