【学习笔记】基(奇)本(技)套(淫)路(巧)

本篇是关于我做题时遇到的很神奇的技巧和思路的总结，会不定时更新。
以后就记录一些小 trick 以及一些知识点的小套路

对于乘除法我们可以直接取对数转化为加减法
对于 \(\lceil \dfrac{a}{b} \rceil\) 可以转化为 \(\lfloor \dfrac{a + (b-1)}{b} \rfloor\) 来快速求解
对于两个点 \(x,y\)，若 \(lca(x,y)\) 为 \(x\)，则意味着 \(x\) 在 \(y\) 到根的路径上。
区间内有无重复元素：记录上一次出现的位置，然后转化为区间取 \(\min\)
将 DP 的转移分为几块，每一块分开处理分开考虑
区间问题转化为差分或前缀和后考虑
对于存在查询很优以及修改很优的做法，就可以考虑使用分块平衡复杂度
边权转点权：每条边额外建一个点，连接这条边的两个端点
枚举每一个数的约数可以逆向转化为枚举每一个数的倍数，就可以让复杂度 \(O(n\sqrt{n}) \to O(n \log n)\)
预处理前后缀信息，通过前后缀信息合并得到答案
与子树相对深度相关的有关的题，将贡献改为与子树绝对深度相关的信息
与某个极大数的组合数相关的题，考虑卢卡斯定理
SAM 中两个前缀的 LCS 是它们在 parent 树上的 lca 的最长串
后缀的 LCP 可以建反串转化为前缀的 LCS
广义 SAM 中一般可以考虑使用线段树合并维护当前点属于的模板串的集合，也可以用来维护 endpos 集合
\(\lfloor \frac{j-i}{k} \rfloor = \lfloor \frac{j}{k} \rfloor - \lfloor \frac{i}{k} \rfloor - [(j \% k) < (i \% k)]\)
树形背包的优化做法的复杂度是 \(O(nm)\)，其中 \(n\) 是节点数，\(m\) 是背包大小
自动机要考虑对模式串建或者询问串建，都考虑一下
链加+单点查询 -> 单点加+子树查询：好写而且复杂度低
对于某些操作或者什么的，可以考虑想想终止状态是什么
期望次数可以理解为 \(\frac{1}{\text{概率}}\)
路径最大值/最小值：Kruskal 重构树；路径最大值最小/最小值最大：最小生成树、二分答案
字符串匹配使用 bitset 维护文本串每一个字符出现的位置，然后模式串求一个并集就好了
计数问题想不出来就考虑容斥一下，容斥原理或者统计不合法的方案数
没啥想法就随便枚举几个值试试
带环 DP：高斯消元、二分一个值
对于两个不同的数，二进制分组之后一定至少有一次它们在不同组中
设 \(p[i]\) 表示为 \(i\) 的概率，\(P[i]\) 表示大于等于 \(i\) 的概率，那么期望可以理解为：\(\sum_{i=1}^n i \times p[i] = \sum_{i=1}^n P[i]\)
\(\sum_{j=0}^i \binom{i}{j} = 2^i\)
平衡树的翻转标记：只要下面有用到他的儿子就下传
树上两条路径如果有公共点，则交集必然满足点数等于边数加一
非必要情况，否则使用树剖求 \(lca\)
根据条件去求满足条件的点，或者枚举点判断是否符合条件
Kruskal 重构树的节点个数为 \(2\times n - 1\)，千万别直接把 \(n\) 拿上去了。