tricks

UniGravity · 2024-07-01 07:47:55 · 个人记录

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