基(奇)本(技)套(淫)路(巧)

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

Tricks

1. 对于乘除法我们可以直接取对数转化为加减法

2. 对于 $\lceil \dfrac{a}{b} \rceil$ 可以转化为 $\lfloor \dfrac{a + (b-1)}{b} \rfloor$ 来快速求解

3. 对于两个点 $x,y$，若 $lca(x,y)$ 为 $x$，则意味着 $x$ 在 $y$ 到根的路径上。

4. 区间内有无重复元素：记录上一次出现的位置，然后转化为区间取 $\min$

5. 将 DP 的转移分为几块，每一块分开处理分开考虑

6. 区间问题转化为差分或前缀和后考虑

7. 对于存在查询很优以及修改很优的做法，就可以考虑使用分块平衡复杂度

8. 边权转点权：每条边额外建一个点，连接这条边的两个端点

9. 枚举每一个数的约数可以逆向转化为枚举每一个数的倍数，就可以让复杂度 $O(n\sqrt{n}) \to O(n \log n)$

10. 预处理前后缀信息，通过前后缀信息合并得到答案

11. 与子树相对深度相关的有关的题，将贡献改为与子树绝对深度相关的信息

12. 与某个极大数的组合数相关的题，考虑卢卡斯定理

13. SAM 中两个前缀的 LCS 是它们在 parent 树上的 lca 的最长串

14. 后缀的 LCP 可以建反串转化为前缀的 LCS

15. 广义 SAM 中一般可以考虑使用线段树合并维护当前点属于的模板串的集合，也可以用来维护 endpos 集合

16. $\lfloor \frac{j-i}{k} \rfloor = \lfloor \frac{j}{k} \rfloor - \lfloor \frac{i}{k} \rfloor - [(j \% k) < (i \% k)]$

17. 树形背包的优化做法的复杂度是 $O(nm)$，其中 $n$ 是节点数，$m$ 是背包大小

18. 自动机要考虑对模式串建或者询问串建，都考虑一下

19. 链加+单点查询 -> 单点加+子树查询：好写而且复杂度低

20. 对于某些操作或者什么的，可以考虑想想终止状态是什么

21. 期望次数可以理解为 $\frac{1}{\text{概率}}$

22. 路径最大值/最小值：Kruskal 重构树；路径最大值最小/最小值最大：最小生成树、二分答案

23. 字符串匹配使用 bitset 维护文本串每一个字符出现的位置，然后模式串求一个并集就好了

24. 计数问题想不出来就考虑容斥一下，容斥原理或者统计不合法的方案数

25. 没啥想法就随便枚举几个值试试

26. 带环 DP：高斯消元、二分一个值

27. 对于两个不同的数，二进制分组之后一定至少有一次它们在不同组中

28. 设 $p[i]$ 表示为 $i$ 的概率，$P[i]$ 表示大于等于 $i$ 的概率，那么期望可以理解为：$\sum_{i=1}^n i \times p[i] = \sum_{i=1}^n P[i]$

29. $\sum_{j=0}^i \binom{i}{j} = 2^i$

30. 平衡树的翻转标记：只要下面有用到他的儿子就下传

31. 树上两条路径如果有公共点，则交集必然满足点数等于边数加一

32. 非必要情况，否则使用树剖求 $lca$

33. 根据条件去求满足条件的点，或者枚举点判断是否符合条件

34. Kruskal 重构树的节点个数为 $2\times n - 1$，千万别直接把 $n$ 拿上去了。

35. 在图论中看到只经过小于等于或者大于等于某个值的条件时，想到 Kruskal 重构树，转化为子树询问

36. 期望 $dp$ 一般可以考虑设到最终状态的期望，也可以是走一步的期望

37. 对于选 $k$ 个元素最优的题，那么对于任意一种最优方案，对于任意一个区间 $[l,r]$ 若区间内选了 $p$ 个，那么这 $p$ 个一定是区间 $[l,r]$ 选择 $p$ 个的最优方案之一。

38. set 里 count 的复杂度是假的，不如直接用 map

39. 1 int = 4b

40. 调题的时候不要着急，要分析问题性质而不是对着错误的数据在那里打补丁。

41. 某类数数题考虑最终的状态满足什么条件时合法，然后统计这些条件就变简单了。

42. 树上 $m$ 个点的 $LCA$ 等于 $dfs$ 最小的点和最大的点的 $LCA$。

43. 可以根据 $dp$ 进行的决策倒推 $dp$ 的状态是什么，也就是为了完成这个决策需要知道什么，以及知道了什么之后才能转移。

44. 矩阵乘法优化 $dp$ 中，如果 $dp$ 是一行左乘的话，转移矩阵的 $(i,j)$ 的值其实相当于 $dp[i]$ 到 $dp[j]$ 的转移系数。

45. 图论中删一度点、缩二度点、叠合重边，能将问题规模缩小就能变得更加好做。

46. 树形 $dp$ 的两种推法：考虑每次添加一棵子树、把所有的子树放在一起考虑，都是有用的，可以按实际情况考虑怎么推。

47. 树上 $ddp$ 其实就是 $son \to u$ 然后再逐一合并 $u$ 的所有子树。

考试犯的傻逼错误：

1. xxxx;xxxx; 却没打大括号
2. 交错源代码
3. 平衡树新建节点一定要把所有的信息都赋初值，不能感觉可以不赋就不赋
4. 注意题目中是说：经过边的数量还是经过点的数量
5. 字符串题注意串的字符串的首地址需要不需要加一
6. 不要轻易否定自己的解法，如果感觉不对就构造一组，跑一遍 hack 掉就好了
7. 网络流里不能随便建双向边，很多题在实际的建模里需要从 S -> T （大致方向）建边。
8. 建文件夹一定只包含数字和字母
9. 可以手模的样例一定要手模
10. 多测一定要清空，是将本次更改的全部改回去，而不是将下次可能用到的改回去，非必要情况，请使用 $memset$ 清空
11. 一定不要读形式化题面，只给了一坨抽象的式子完全不如慢慢读文字题面
12. 数组中长度小的维度放在前面，可能可以让速度快很多倍
13. 一定要认真读数据范围，特别关注看上去就很不正常的地方
14. 预处理阶乘的逆元一定要记得处理 $0$ 的啊。
15. 平衡树不要和线段树混了，记得 $now$ 也是一个独立的点啊
16. 无法调试或者灵异事件不要着急：观察一下基本的配置、观察一下文件（夹）名
17. 传参数不要直接传一个 $vector$
18. multiset 删除一定要反复检查是不是直接 erase(x)
19. 状压或枚举状态的时候一定要注意从 $0$ 开始还是从 $1$ 开始，就是需不需要减一
20. 写复杂的数据结构一定要从内层到外层慢慢来，千万不要从外层到内层去写
21. 一些主函数比较难写的数据结构，就先把数据结构用暴力实现，直到主函数改对再去写数据结构
22. 多测清空的时候注意：是不是之前的一些特判直接跳过了清空环节
23. 要先有一个正确性有保证的做法，然后再有一个复杂度有保证的做法