• 学习笔记

    欧拉回路学习笔记

    下面的内容主要是是搬运的陈通的集训队论文,可能会有点私货和代码(大雾)。 论文链接 基本概念 定义1.1:图 $G$ 中经过每一条边恰一次的回路称为欧拉回路,经过每条边恰一次的路径称为欧拉路径。 定义1.2:存在欧拉回路…

  • 学习笔记

    2-SAT学习笔记

    SAT,即为适定性(Satisfiability)问题。通俗来讲就是给定n元素,每个元素都有k取值。然后给定m限制条件,问是否有满足所有限制条件的取值方案,若有则给出一组可行的方案。若每个元素最多k种取值,则称之为K-S…

  • 学习笔记

    位运算(一)

    简介 计算机中的所有数据都是以二进制的形式存储的,位运算就是直接对这些二进制数据进行操作,因此处理速度非常快。 基本的位运算 & 按位与运算,当两个位都为1时,结果才为1。 例如11 & 13,这两个数转…

  • 学习笔记

    【模板】ST表

    简介 ST表,稀疏表,用于求解经典的RMQ问题。即区间最值问题。基于倍增思想,利用递推的方式预处理,支持高效的查询,不支持修改 代码 #include <cstdio> #include <cmath&…

  • 学习笔记

    二分图学习笔记

    二分图又称二部图,是图论中一种特殊模型。对于一个无向图,如果可以把他的顶点分为两个互不相交的子集,并且图中的每一条边,所关联的两个顶点都分别属于两个不同的顶点集,则称该图为二分图。显然二分图中不存在奇数环,如果出现的话无…

  • 学习笔记

    【模板】线段树

    概述 线段树是一种二叉搜索树,用来维护区间内的符合区间加法的值,支持高效的查询与修改操作。每一次操作的时间复杂度是 $O(log_2N)$ 原理 线段树把区间 $[l,r]$ 成了 $[l,mid]$ 与 $[mid+1…

  • 学习笔记

    【模板】01背包

    $f[i]$表示背包已用i容量时能得到的最大价值,value[i]表示第i个物体的价值,size[i]表示第i个物品所要占据的背包容量(或者说是重量、时间之类的)。那么我们的决策就是要不要把当前处理的物品放入背包中。我们…