__故人__

算法模板

CF(8) UOJ(1) 每日一题(3) 牛客小白月赛27(10) 随笔(20) 题解(117)

/ 注册

全部文章 / 算法模板（共10篇）

倍增例题

相信大家初步了解了倍增之后，想要实践一下。这里选取了牛客的例题来讲解。来个👍 呗，。入门知识传送门一些简单规定指图上的最短路，在树上为的简单路径。指有根树上的深度。 [AHOI2008]MEET 紧急集合题意给出三个点，找到一个节点使最小。分析我们考...

2020-11-26

10 1074

倍增

说在前面的本人实力不高，求大佬轻喷，我尽量讲清楚一点。例题传送门在未作说明的情况下，有根树都以为根。表示，节点的最进公共祖先。表示，节点的深度。表示，节点的树上简单路径长度。倍增倍增法（英语：），顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，...

2020-11-25

14 764

组合数学和斯特林数

写在前面的本博客基本不会讲解如何运用组合数和斯特林数，应该偏向于数学证明，各类恒等式，我先咕一咕。更新日志 11.17 基本的组合恒等式。 11.18 反演原理（很多反演放在后面讲解）。 11.18 第一类斯特林数。 11.18 第二类斯特林数。 11.18 二项式反演，斯特林反演。定义 ...

2020-11-17

9 830

点分树

说在前面的我一看到是点分树，马上就点进来了，很快啊。前置知识：点分治。约定表示的树上路径长度。引入给出一颗个点的树，每个点有一个权值，有两种操作，一种是将某个点的权值修改为，另一种是查询距离点不超过的点的权值和。分析我们考虑暴力，如果将一个操作的复杂度降...

2020-11-13

9 746

带权二分

前面的话这篇博客大概是带权二分(wqs 二分，是叫这个名字吧)的入门博客，希望大家点个赞👍。引入给你一个序列。其中。可以把序列分为段。定义每一段的价值为，现在要求的总和最小。形式的，我们要最小化。分析我们可以先做一个的线性。定义为结尾，分了的...

2020-11-11

8 572

拉格朗日乘数法求函数的最值

写在前面的这个是个好东西啊，好东西啊（神志不清）。这个方法可以非常简单的求出多元函数的条件最值，而且不需要动脑子，会求导就完了。引入求的最小值。其中。如果使用柯西不等式就一步。。拉格朗日乘数法的大体步骤为。令条件函数，和目标函数。分别对所有变量求出偏导。令偏导为 ...

2020-11-10

4 2945

树上dfs序小专题

说在前面的和欧拉序都是非常有力的工具，我们应该熟练的运用两者。而且序也不必局限于树上的序，其实一般图也有序，有兴趣的朋友可以参考算法。以下的序，全部指树上的序，序即使在树上，仍然不是唯一的。以下的，全部指以为根，子树的大小。 dfs 序引入如何判断...

2020-11-09

9 892

点分治

写在前面的一起对于简单点分治的题都是用解决的，结果遇到点分树，哦吼，做不来了。这才打算学一下点分治，我检讨。点分治引入给你个询问，询问一个树上是否有长度为的路径。要求在时间复杂度内解决。如果学习过的同学，这个就是个模板。但是这里还是考虑使用点分治解决。其实这两个算法我...

2020-10-28

1 613

01 Trie 解决异或小专题

说在前面的我希望以后的每日一题也是以小专题出现的，我觉得这样的练习效果才好。而且题有点少，并且有很多重复。例如解决异或和，权值，合并没有出现，有点小伤心。牛客工作人员找了这么多的例题真的很辛苦。感谢牛客。异或异或是一种位运算。满足。这个比较好理解，大概就是两个数异或，那么在一位...

2020-10-25

8 835

最小直径生成树

图片来源与引入这个是一个比较偏门的算法，但是并不排除考察的可能性。其中的思路比较灵活，这里介绍一下，希望起到抛砖引玉的效果。图的绝对中心概念，图的绝对中心可以存在于一条边上或某个结点上，该中心到所有点的最短距离的最大值最小。那么我们首先的关键点就是求出图的绝对中心，我们可以分类讨论，...

2020-10-06

4 833