套路总结¶
区间覆盖¶
如果使用差分的方式完成，最后一个点后的值可能为 \(0\)，要考虑这个值有没有可能不是任何一个区间的值。
树状数组¶
在维护一些不可减的东西的时候，有可能存在特殊性质使得维护的东西实际上是前缀或后缀，此时可以使用树状数组代替线段树，减少常数和代码复杂度。
修改和查询都反过来就可以维护后缀和。
矩阵快速幂¶
可以维护一堆数字符号拼接在一起组成的表达式。
多边形¶
判断一个点是否在多边形内部不要使用判四个方向能不能碰到边界，会被凹多边形制裁。
Min_25 筛¶
数位 dp¶
差分约束¶
floyd 也可以跑差分约束，spfa 跑出来的只是一组可行解，而 floyd 跑出来两点间的距离就是对应两个值的最大差值。另外，floyd 判负环可以直接遍历所有点看自己到自己的距离是否为负数。
二进制分组¶
二进制分组可以用 \(O(\log n)\) 个物品跑 01 背包覆盖 \([0,n]\) 的所有物品取值，但是对于 \([0,n]\) 的每个物品取值，方案并不是唯一的。
AC自动机¶
设字符串总长为 \(n\)，则 fail 树的高度不超过 \(O(\sqrt n)\)。
行列式函数求导¶
\[
\begin{aligned}
\frac{\text d}{\text dx}|\boldsymbol{A}(x)|&=|\boldsymbol{A}(x)| \text{Tr}\left(\boldsymbol{A}^{-1}\frac{\text d \boldsymbol{A}(x)}{\text d x}\right) \newline
&=|\boldsymbol{A}(x)| \sum_i \sum_j {\left(\boldsymbol{A}^{-1}(x)\right)}_{ij}{\left(\frac{\text d \boldsymbol{A}(x)}{\text d x}\right)}_{ji}
\end{aligned}
\]
这里矩阵函数对单个变量的求导 \(\dfrac{\text d \boldsymbol{A}(x)}{\text d x}\)，即为矩阵中每个位置分别对 \(x\) 求导。
具体证明：行列式求导法则。
二分图最大权匹配¶
KM 算法：给每个顶点分配一个顶标，使得对于任意一条边，两侧点的顶标之和不小于该边的权值。
使用费用流求最大权匹配的时候左侧的点也要和汇点连边，因为最大权匹配不一定是最大匹配，但是我们跑的是最大费用最大流，所以一定要让没匹配上的点也流向汇点。