0 总

• 刚开始时首先打对拍，迟早要用上。
• 开题之后先写暴力。
• 该开 long long 就开 long long，不要想着卡常。
  • 问一下自己要不要开 __int128。
• 要有好的调试习惯，写好的代码必须去评测环境下测一下样例防止 CE。
• 模意义下问题一定要打 modint。
  • 注意指数对 $p-1$ 取模。
• 需要精确的分数但不需要比较分数大小时，可以直接对大质数取模，用逆元避免精度问题。
• 警钟撅响 在比赛的最后要确保自己提交的是自己想交的那份代码。
• 遇到强制在线，看看能不能偷鸡。（P10774）

时间复杂度考虑

• 在 $10^{18}$ 内，$d(n)$ 约等于 $n^{\frac 1 3}$。
• 看到 $10^{18}$ 考虑 $O(\log n)$ 和 $O(d(n))$。
• 看到 $50$ 考虑 $O(p(n))$。$p$ 为拆分数 A000041。
• 看到 $30$ 左右考虑折半搜索。

1 序列上统计

• 考虑摊贡献。
• 形如”对于所有子区间 $[l,r]$”的题，考虑分治。（AT_abc159_f）
  • 若询问与 $\min, \max$ 都有关，可以讨论 $\min, \max$ 分别出现在 $mid$ 的哪边。
• 考虑元素顺序是否对答案有影响。
  • 若无影响，考虑排序 / 开桶。
  • 若开桶，考虑调和级数。（AT_abc356_e, AT_abc177_e）
• 括号匹配考虑匹配栈。
  • 匹配栈可以搭配哈希。（CF1223F）
  • TRICK 如果不区分左右括号，考虑矩阵哈希。（CF1223F）

2 贪心

猜结论，写对拍。OI 赛制下一定要写对拍！富有恶意的出题人可能会设置非常弱的样例。不要考虑怎么证明策略正确性。

乱搞：把能想到的贪心策略全做一遍，答案取所有结果的最大 / 最小值。对顺序没有要求的题，shuffle 之后再乱贪。

• 位运算题考虑贪心。
  • 有权值为 $2^i$ 的题目直接贪心。
• 字典序题直接贪心。
• 设计贪心，可以从一个最初始的情况开始慢慢往上加。（AT_abc359_f）
• 警钟撅响 STL 容器要判空。
• TRICK 优先队列被卡时，考虑换普通队列。（P6033, P2827）

3 最优化

• 首先考虑二分。
  • 例如 01 分数规划。
• 二分不行，考虑贪心。

4 位运算

• 位运算题有三种套路：拆位、01 Trie、线性基。
• 不管用的是哪个套路，考虑贪心。

5 DP

• 答案数远小于状态数，考虑反着设状态。（AT_dp_e）
• 状态数跑不满考虑记搜，万一降复杂度了呢。
• 计数题实在不会的话，考虑 GF。（AT_abc358_e）
• 字符集很小（一般为 $26$ 或 $52$）时，把字符加入状态设计。

6 数据结构

• 遇到”删除”“分离”等，且允许离线，考虑时光倒流，转化为”加入”“合并”。（P1197）
  • 也可考虑线段树分治。
• 遇到”合并”，考虑启发式合并。（P3359）

莫队

• 区间查询，不带修，直接莫队。
  • 警钟撅响 块长设为 sqrt(n)，不要设 n / sqrt(m)（可能会为 $0$）。

序列并查集

• 形如”初始时所有点不染色，每次操作染色一个区间 / 一个点”的题目，考虑序列并查集。（P1840, P4092）

平衡树

• 想到平衡树做法，首先考虑 map 和 set 能不能实现。
  • 若不能，直接 pbds。

可持久化线段树

• 离线可以使用线段树（树状数组）扫描线完成的题，在线可以考虑可持久化线段树。

7 树

• 关于树上的多条路径的题目，考虑 LCA。
  • LCA 分类讨论不清楚的话，直接把能想到的所有条件写上去，肯定不会错。
  • 简单结论 对于树上的四个点 $A,B,C,D$，$A \rightsquigarrow B$ 与 $C \rightsquigarrow D$ 有交当且仅当 $LCA(A,B)$ 在 $C \rightsquigarrow D$ 上或 $LCA(C,D)$ 在 $A \rightsquigarrow B$ 上。（P3398）
  • 简单结论 对于树上的三个点 $A,B,C$，记 $LCA(A,B), LCA(A,C), LCA(B,C)$ 中深度最深的为 $P$，则 $A \rightsquigarrow B$ 与 $C \rightsquigarrow B$ 的交集为 $P \rightsquigarrow B$。（权限题 XMOJ4716）
• 树上背包的复杂度是 $O(nm)$。
• 无根树统计，考虑换根 DP。
• 树上最远点，考虑直径。
  • TRICK 结论 边权非负时，对于树上每个点 $i$ 求离它最远的点，可以先求一条直径 $a \rightsquigarrow b$，答案即为 $ans_i = \max(\text{dis}(a,i), \text{dis}(b,i))$。
• 子树问题，考虑把树拍到 DFS 序上。
• 点集的导出子树，考虑把点集按 DFS 序排序。（P3320）

8 图论

• 警钟撅响 注意图不连通和孤立点。
• 有一个量数据范围特别小，考虑分层图。
• 但凡图有一点特殊性质，都可考虑 SPFA。
• 图上走 $k$ 步，考虑矩阵快速幂。
  • TRICK 考虑搭配矩阵乘向量食用。（P6772）

MST

• 点有点权时，建模可以把点权加入边权。

最短路

• 点有点权时，建模可以把点权加入边权。

差分约束

• 警钟撅响 开超级源点，SPFA 的入队次数要达到 $n+1$ 才算无解。

基环树

• 遇到基环树不要首先想着 DFS，可以用 Tarjan 缩掉那个环。（AT_abc357_e）

9 排列组合

• $\binom n m = \frac {n^{\underline m}} {m!}$ 可以 $\Theta(m)$ 计算，适用于 $n$ 巨大的情况。
  • 优秀的实现
• 计算二项式系数不要只想着 $\frac {n!} {m! (n-m)!}$，数据范围小的时候可以杨辉三角。
• 遇到”恰好”考虑容斥原理 / 二项式反演。（P10596）

10 数学 / 数论

• 警钟撅响 log10 等浮点数函数在 long long 范围内会有精度误差（ABC357D）
• 警钟撅响 等比数列求和特判公比为 $1$（P4948）
• 没思路时直接打表。
• 出现 $\sum\limits_{i} f(\gcd(i,n))$，转成枚举 $\gcd$。
• 拆 $d(nm)$ 这样的结构时，因为积性函数所以令 $n=p^a, m=p^b$，然后再推。

BSGS

• 矩阵也可 BSGS。（P3306）

同余最短路

TODO: 还不会啊怎么办。但是感觉也不多见。

11 字符串

Hash

• 遇到字符串题首先考虑 Hash。
• 注意生日悖论。
• 括号匹配可以考虑矩阵 Hash。（P9753）
  • 当然，首先应当考虑匹配栈。（P9753）
• 回文串问题枚举对称轴然后二分。

KMP / AC 自动机

• KMP / AC 自动机上也可以做 DP。（P3193）
  • 作为图上 DP，在数据范围较小时可以考虑矩阵加速。（P3193）

12 计算几何

• 警钟撅响 与直线有关的计算几何题，特判点数 $n=1$。（P1142）

计算几何（假）

• 形如”平面被分成几块”的问题，考虑欧拉公式 $V - E + F = 2$。
• 关于整点多边形的问题，考虑 Pick 定理。（P2735）
• 矩形考虑扫描线。
• TRICK 遇到曼哈顿距离 / 切比雪夫距离首先考虑互相转换。（P3964, P5098）

计算几何（真）

• 考虑随机旋转人类智慧。（P1429）

13 其它

• 警钟撅响 使用 map 或 set 时，考虑是否有重复元素（此时使用 multimap 或 multiset）（ABC358D）
• TRICK 高精度题考虑对多个质数取模。（P2312）
• TRICK 全是乘除法的题目，考虑取对数。（P4926）
  • TRICK 若是模意义下，可通过原根取对数。（CF487C）
• TRICK 结论 $x < y < z$，则 $\min(x \oplus y, y \oplus z) < x \oplus z$。（AT_abc308_g）
• （Trivial）$a \ge b$，则 $\gcd(a,b) \le a-b \le a \oplus b \le a+b$。（UVA12716）
• TRICK 结论 $\gcd(f_n, f_m) = f_{\gcd(n,m)}$，其中 $f$ 为 Fibonacci 数列。（P1306）
• TRICK 结论 Fibonacci 数列在模 $m$ 下的循环节长度 $\pi(m) \le 6m$。（P4994, P4000）
  • 如果真的遇到了其它递推数列，直接信仰其循环节为 $O(m)$。
• 遇到绝对众数，首先考虑摩尔投票，其次考虑随机化。（P3765）