二分图 我们就考虑，对于一个二分图来说，用超源连接一下左面的点，超汇连接右边的点，然后跑一边最大流，就是二分图最大匹配 定理： 二分图最大匹配=二分图最小点覆盖 有向无环图最小不相交路径覆盖 有向无环图最小可相交路径覆盖 二分图的最大独立集等于总点数减去最大匹配等于最小边覆盖 P2756 简单的二分图 左边点是外籍，右边是嘤籍 跑最大匹配 然后...

单调队列优化dp 刷题记录哦（by能力提升综合题单 多重背包 我们考虑，普通的多重背包是什么样子的 f[j]=max(f[j−v[i]∗k]+w[i]∗k)(k≤num[i])f[j] = max(f[j-v[i]*k]+w[i]*k)(k\le num[i])f[j]=max(f[j−v[i]∗k]+w[i]∗k)(k≤num[i]) 我们考虑一...

概率 离散型随机变量：只有有限种可能值的随机变量 连续型随机变量：随机变量 x 的分布函数可以表示成一个非负可积函数 f(x) 的积分 对于同一样本空间下的互斥事件，P(A+B)=P(A)+P(B)P(A+B) = P(A)+P(B)P(A+B)=P(A)+P(B) 推论：对于全部的基本事件来说∑P(ei)=1\sum P(e_i)...

导数 定义：我们把x在一段极小趋近于0（有限小）的时间内变化的量称为dx，记住是极小的时间而不是无穷小 那么函数f(x)f(x)f(x)的导数便是：dfdx\dfrac{df}{dx}dxdf​，可以简记成f′(x)f'(x)f′(x) 当然导数有多种求法，一种是代数求法，还有一种几何求法，就比如指数函数，都可以用……（抽象成几何体就好了...

树剖 一个神奇的数据结构 树链剖分，顾名思义就是把一棵树解剖成一些链 我们先来几个定义： 重儿子：对于一个节点来说，他的儿子们中子树体积最大的儿子称为他的重儿子 重边：两个重儿子连起来的边 重链：很多条重边连起来形成的一条链 轻儿子：除了重儿子之外的儿子 轻链：类比一下 我们会发现，重儿子是可以一遍dfs求出来的，我们会发现一个很重要的性质： 在d...

主席树 全称为：可持久化线段树 我们考虑一件事情，如果说我们对于一个线段树来说，希望它可以查询一些修改之前的序列（我们称之为历史版本） 我们当然可以每一次把线段树复制一遍，但是时空复杂度并不能够接受 所以我们应该进行一些可持久化的处理： 我们发现对于单点修改来说，线段树最多改变的就是log2n个节点 所以我们可以把更改的几个节点单独拿出来存储起来，...

分块大法好啊 分块，顾名思义，就是一种把序列分成若干个块的算法（数据结构） 前段时间的时候写的分块，调到怀疑人生，结果今天开始学主席树了发现我爱分块 分块的思想简称就是：大块维护，小块朴素 P3396 哈希冲突 我们先假设一下，如果说模数是小于等于n\sqrt{n}n​的时候，我们是不是可以预处理出来所有模数对应的答案（更改很容易的） 然后我们再想...

AC自动机 阅读本章之前应该具备的前置知识：KMP（其实并不是很重要但是还是要会的），trie字典树 首先对于若干的模式串我们把它插入到一个trie树中，我们考虑，对于一个非常水的模板题： 对于一个文本串，计算所有模式串在其中出现次数的总和 我们考虑把这个文本串在这个trie树上面跑一遍（像是插入一样 但是我们发现，如果说我们当前匹配的时候发现失配...