tricks
UniGravity · · 个人记录
algorithm tricks
basic
-
max(a,b)+c=\max(a+c,b+c) - 使用随机化 check 排列。
data structure
dp
- 组合意义保平安。
- 当
dp_{i,j,k} 只需要考虑j 和k 的相对大小时,其可以转化成dp_{i,j-k} 。 - 对于一个每一位递增的数
11223444 可以拆成11111111+111111+1111+111 。\tiny\textbf{神仙思路} math
- 一个数最多有
1 个大于等于\sqrt n 的质因子。\tiny\textbf{常用于状压 dp} - 随机旋转坐标!
\tiny\textbf{充分发扬人类智慧} graph
- 判定树:
ecnt_i>0 且\sum ecnt_i=2(n-1) - prufer 拓展:连通块生成树个数
n^{k-2}\prod_{i=1}^kc_i network flow
- 网络最大流
= 二分图最大匹配= 二分图最小点覆盖=n\ - 二分图最大独立集。 - 平面图最小割
\leftrightarrows 对偶图最短路string
poly
coding tricks
basic
data structure
dp
math
long long多取模,__int128少取模。graph
- 链式前向星二倍空间。
network flow
string
poly