__故人__
__故人__
全部文章
算法模板
CF(8)
UOJ(1)
每日一题(3)
牛客小白月赛27(10)
随笔(20)
题解(117)
归档
标签
去牛客网
登录
/
注册
__故人__的博客
我太菜了/kk
全部文章
/ 算法模板
(共10篇)
倍增例题
相信大家初步了解了倍增之后,想要实践一下。这里选取了牛客的例题来讲解。来个👍 呗, 。 入门知识传送门 一些简单规定 指图上的最短路,在树上为 的简单路径。 指有根树上的深度。 [AHOI2008]MEET 紧急集合 题意 给出三个点 ,找到一个节点 使 最小。 分析 我们考...
2020-11-26
10
1332
倍增
说在前面的 本人实力不高,求大佬轻喷,我尽量讲清楚一点。 例题传送门 在未作说明的情况下,有根树都以 为根。 表示,节点 的最进公共祖先。 表示,节点 的深度。 表示,节点 的树上简单路径长度。 倍增 倍增法 (英语: ),顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理,...
2020-11-25
14
929
组合数学和斯特林数
写在前面的 本博客基本不会讲解如何运用组合数和斯特林数,应该偏向于数学证明,各类恒等式,我先咕一咕。 更新日志 11.17 基本的组合恒等式。 11.18 反演原理(很多反演放在后面讲解)。 11.18 第一类斯特林数。 11.18 第二类斯特林数。 11.18 二项式反演,斯特林反演。 定义 ...
2020-11-17
9
1110
点分树
说在前面的 我一看到是点分树,马上就点进来了,很快啊。前置知识:点分治。 约定 表示 的树上路径长度。 引入 给出一颗 个点的树,每个点有一个权值,有两种操作,一种是将某个点的权值修改为 ,另一种是查询距离点 不超过 的点的权值和。 分析 我们考虑暴力,如果将一个操作的复杂度降...
2020-11-13
9
960
带权二分
前面的话 这篇博客大概是带权二分(wqs 二分,是叫这个名字吧)的入门博客,希望大家点个赞👍。 引入 给你一个序列 。其中 。可以把序列分为 段。定义每一段的价值为 ,现在要求 的总和最小。形式的,我们要最小化 。 分析 我们可以先做一个 的线性 。定义 为 结尾,分了 的...
2020-11-11
8
719
拉格朗日乘数法求函数的最值
写在前面的 这个是个好东西啊,好东西啊(神志不清)。这个方法可以非常简单的求出多元函数的条件最值,而且不需要动脑子,会求导就完了。 引入 求 的最小值。其中 。 如果使用柯西不等式就一步。 。 拉格朗日乘数法的大体步骤为。 令条件函数,和目标函数。 分别对所有变量求出偏导。 令偏导为 ...
2020-11-10
4
3421
树上dfs序小专题
说在前面的 和欧拉序都是非常有力的工具,我们应该熟练的运用两者。而且 序也不必局限于树上的 序,其实一般图也有 序,有兴趣的朋友可以参考 算法。 以下的 序,全部指树上的 序, 序即使在树上,仍然不是唯一的。 以下的 ,全部指以 为根,子树的大小。 dfs 序 引入 如何判断...
2020-11-09
9
1064
点分治
写在前面的 一起对于简单点分治的题都是用 解决的,结果遇到点分树,哦吼,做不来了。这才打算学一下点分治,我检讨。 点分治 引入 给你 个询问,询问一个树上是否有长度为 的路径。要求在 时间复杂度内解决。 如果学习过 的同学,这个就是个模板。但是这里还是考虑使用点分治解决。其实这两个算法我...
2020-10-28
1
764
01 Trie 解决异或小专题
说在前面的 我希望以后的每日一题也是以小专题出现的,我觉得这样的练习效果才好。而且题有点少,并且有很多重复。例如 解决异或和,权值 ,合并 没有出现,有点小伤心。牛客工作人员找了这么多的例题真的很辛苦。感谢牛客。 异或 异或是一种位运算。满足 。这个比较好理解,大概就是两个数异或,那么在一位...
2020-10-25
8
1064
最小直径生成树
图片来源与 引入 这个是一个比较偏门的算法,但是并不排除考察的可能性。其中的思路比较灵活,这里介绍一下,希望起到抛砖引玉的效果。 图的绝对中心 概念,图的绝对中心可以存在于一条边上或某个结点上,该中心到所有点的最短距离的最大值最小。 那么我们首先的关键点就是求出图的绝对中心,我们可以分类讨论,...
2020-10-06
4
990