二叉搜索树简介A Brief Introduction 二叉搜索树Binary Search Tree是一种特殊的二叉树，它有如下的性质： 左儿子（如果存在）的节点值比当前节点的值要小 右儿子（如果存在）的节点值比当前节点的值更大 某个节点的左/右子树（如果存在）也为一个二叉搜索树 中序遍历得到的节点值序列是不下降的（属于是推论） 二叉搜索树是很多重要树形数据结构的理论基础，例如树堆Tr...

前言 他只需略微现身，考生瞬间变圆神；只需给他一个不定参，他能把数学题做成英语题；给他一个定值证明，他能逼出考生使用伪证大法。不是含参韦达算不起，而是伪证算法更有性价比。有人说椭圆双曲线简单，新高考I卷丝带线表示不服。对此，五星上将麦克阿瑟评价道：“如果当年美军的考试卷没有圆锥曲线压轴题，美军战士一定能在圣诞节之前回家”。那么，圆锥曲线到底有何魔力？大型纪录片《圆锥曲线传奇》持续为您播出……...

差分约束系统 理论基础 我们称形如下面给出的多元一次不等式组为一个差分约束系统： 它包含 个未知数，以及 个约束条件，每个约束条件是由两个未知数作差构成的不等式。 求解这个不等式组，我们首先考虑移项，例如第一个不等式变成：。联想到最短路的三角不等式，即 ，这个方程组可以转化为一个最短路问题。具体到第一个不等式，就是创建边 ，边权为 。在读入所有不等关系后在建出的图上做最短路即可。 最短...

前言 在写 SPFA 判负环 的时候发现很多题目需要联系到高贵的0/1分数规划，但是截至当时我还没有学这样优雅的算法，故先将 咕一咕，把关于分数规划的东西弄清楚再回去填坑。正好刚考完高一下的合格考，觉得正是适合学新东西的时候，在此归纳一些简单的分数规划知识……这都什么跟什么啊 分数规划基本模型如下： 给出有 个元素的两个数列 和 ，求对整数 ，使得下式最大化： 通俗一点地说，给出...

关于 SPFA，以及…… ……以及它死了，现在有意无意卡 似乎已经成为 OI 出题界的常规操作了…… 算法的流程如下： 遍历 个点 对于当前的点 ，遍历它的所有出边，并获取出边相连的点 进行松弛操作，将 设为 若终点的最短路长度不为正无穷，则找到最短路；否则整张图不连通 但是在第三步中，每个点的最短距离不一定能够被更新——只有上一次松弛成功的点连接的边，才有可能引起下一次更新...

前言 我非常喜欢一些奇技淫巧，每次有机会时就想用点小技巧，既方便了自己、有时还能博来他人的赞叹，实属一举两得的行为。在这篇文章之前，我的奇技淫巧仅局限于高中数学题。接下来我把进入 C++ 编程以来收集的实用小技巧全部放在这里，并不定时更新新的小技巧。希望能帮到后人。 引用伟大的毛主席的一句话： 幸亏古人和外国人替我们造好了这许多符号，使我们开起中药铺来毫不费力。 毛泽东 ——《反对党八股》...

生成树基础 生成树，在 OI 中最多的考法有两种——最小生成树和次小生成树。最小生成树（Minimum Spanning Tree，MST）是最常见的问题，它是原图边权之和最小的生成树（不一定唯一）；而次小生成树，分为严格次小生成树和非严格次小生成树，前者要求次小生成树的权值和严格小于最小生成树的权值和，后者则无此要求，即允许“大于等于”情况的出现。实际考察严格次小生成树较多。 生成树基础算...

又名：端午游寄——三傻大闹写字楼归还充电宝传奇 六月九日，端午假期的第二天。我们班的几名同学聚集到一起，纷纷拿出高三不要的麦当劳高三助力免费兑换券，准备对凤凰大街的麦当劳进行一次蓄谋已久的劫掠。六个人，每个人平分得到了两张券，朵颐了两个汉堡。便是午后，按原定计划，应该是找个台球厅混一下午。然而计划临时有变，有两名新同学约在天府红商场。于是送别三名同学，我、gz和猴子便前往地铁站准备乘地铁前往...

Floyd 算法简介 Floyd 算法是一种能在 时间复杂度内求出任意两点间最短路长度的多源最短路算法，又称 算法或插点法，以它的发明者命名。Floyd 算法基于动态规划，通过穷举 节点和 节点的所有中继节点 进行松弛操作得到最短路径。对于稠密图，它的执行效率会快于 Dijkstra 和 Bellman-Ford 算法。 在初始建图时。对于邻接矩阵 ， 代表 和 点间的直连最短...

分层图简介 分层图，顾名思义。是将原图按不同状态分为若干与原图连接方式相同的图层，图层之间以特定方式连接的一类建图方式。如果画成立体图，大概是这样的： 根据如上思路，可以发现分层图有以下的几个性质： 假设原图位于 层，总共有 层图。那么对于任意 ，层 内的节点之间的连接方式与 层是完全相同的（与原图连接方式相同）；但是层与层之间的连接方式不一定相同，具体取决于题意 假设不考虑节点...