总

• 刚开始时首先打对拍，迟早要用上。
• 开题之后先写暴力。
• 问一下自己要不要开 long long。
  • 问一下自己要不要开 unsigned long long。
  • 问一下自己要不要开 __int128。
• 有无解要记得骗分。
• 检查 freopen 都写好了没。
• 检查暴力都拼上了没。
• 检查文件都删了没。
• 检查函数返回值都写了没。
• 算内存。

• 测一测极限数据。2log 如果卡常的话看看能不能优化到 1log（可能借助小 $

  \Sigma

  $）。

• 检查会不会爆精度。
  • 如果不卡常的话，某些 double 可以换成 long double，EPS 可以开到 1e-12 之类的。
• 警钟撅响 在比赛的最后要确保自己提交的是自己想交的那份代码，而且要确认暴力写完了之后真的拼上去了。
• 警钟撅响 确认对拍是否会因为随机性而丧失效果。
  • 例：求两串 LCS（字符集巨大），直接随机的话答案几乎只会是 $0$。

对拍

TODO:

小思路

• 考虑答案是否仅与差分数组有关。若是，则差分。
• 考虑答案是否与顺序有关。若否，则排序 / 开桶。
  • 若开桶，考虑调和级数。（AT_abc356_e, AT_abc177_e）
• TRICK 需要精确的分数但不需要比较分数大小时，可以直接对大质数取模，用逆元避免精度问题。
• 手搓样例测试暴力，如果搓样例时感觉受限，考虑根号分治能不能做。
  • 例：权限题 XMOJ8871，造样例时会明显感觉被 $\sum sz_i \le 2n$ 所限制，其实可以根号分治。

时间复杂度考虑

• 在 $10^{18}$ 内，$d(n)$ 约等于 $n^{\frac 1 3}$。
• 看到 $10^{18}$ 不仅要考虑 $O(\log n)$，还可能是 $O(d(n))$。
• $\omega(n)$ 很小，可能能用指数级算法。
• $10^6$ 不一定是 $\text{polylog}$，可能是三次根号 $O(n \sqrt [3] n)$。

序列上统计

• 考虑摊贡献。
• 形如”对于所有子区间 $[l,r]$”的题，考虑分治。（AT_abc159_f）
  • 若询问与 $\min, \max$ 都有关，可以讨论 $\min, \max$ 分别出现在 $mid$ 的哪边。
• 括号匹配考虑匹配栈。
  • 匹配栈可以搭配哈希。（CF1223F）
  • TRICK 如果不区分左右括号，考虑矩阵哈希。（CF1223F）
• 挖掉一处后计算答案
  • 第一种手法：处理前缀后缀答案拼起来。
  • 第二种手法：像线段树一样拆成 $\log$ 段。

贪心

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

• 把能想到的贪心策略全做一遍，答案取所有结果的最大 / 最小值。
• 考虑邻项交换。
• 设计贪心，可以从一个最初始的情况开始慢慢往上加。（AT_abc359_f）
• 位运算题考虑贪心。
  • 有权值为 $2^i$ 的题目直接贪心。
• 字典序题直接贪心。
• 警钟撅响 STL 容器要判空。
• TRICK 优先队列被卡时，考虑换普通队列。（P6033, P2827）

位运算

• 贪心。
• 五个套路：
  • 拆位。
  • 01 Trie。
  • 线性基。
  • SOSDP。
  • FWT。
• $x \bmod \text{lowbit}(x) = 0$。
• $[\text{lowbit}(x) = 2^k] = [x \bmod 2^{k+1} = 2^k]$。

DP

• 答案数远小于状态数，考虑反着设状态。（AT_dp_e）
• DP 优化不了的时候重设状态。

• $

  \Sigma

  $ 很小时，把 $

  \Sigma

  $ 加入状态设计。

• 计数题，考虑正难则反。
• 计数题实在不会的话，考虑 GF。（AT_abc358_e）

数据结构

• 区间查询，不带修，考虑莫队。
  • 警钟撅响 块长设为 sqrt(n)，不要设 n / sqrt(m)（可能会为 $0$）。
• 遇到”删除”“分离”等，且允许离线：
  • 考虑时光倒流，转化为”加入”“合并”。（P1197）
  • 也可考虑线段树分治。
• 遇到”合并”，考虑启发式合并。（P3359）
• 偏序降维 $\rightarrow$ 时间轴。
• 序列插入考虑平衡树和块状链表。
• 区间 $k$ 大不只有可持久化线段树，还有二分答案。（P4278）
• TRICK 颜色段均摊：只有推平时，珂朵莉树一次推平的区间数量均摊为 $O(1)$。
• TRICK 只有区间染色，考虑时光倒流后序列并查集。（P1840, P4092）

可持久化线段树

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

树

• 先考虑链。
• 子树问题，考虑把树拍到 DFS 序上。
• $u,v$ 的 LCA 可以看成：把根到 $u$ 的路径上全部节点染色，求 $v$ 的最近染色祖先。
  • 同理，$dep_{\text{LCA}(u,v)}$ 可以看成根到 $v$ 的路径上的染色节点个数。（P4211）
• 树上连通块数等于点数减边数。
  • 树上一个东西是连通块，当且仅当 $V - E = 1$。
• 一个点集的 LCA 是其中 $dfn$ 最小和最大的两个点的 LCA。（CF1062E）
• 树上背包的复杂度是 $O(nm)$。
• 树上最远点，考虑直径。
  • TRICK 结论 边权非负时，点 $i$ 离它最远的点离它的距离为 $\max(\text{dis}(a,i), \text{dis}(b,i))$，其中 $a \rightsquigarrow b$ 是直径。
• 点集的导出子树，考虑把点集按 DFS 序排序。（P3320）
  • 类似于虚树的思想。
• $\sum deg_u = \Theta(n)$，可以用于根号分治。（ABC350G）

图论

• 警钟撅响 注意图不连通和孤立点。
• 有向图正图难做考虑建反图。
• 遇到基环树不要首先想着 DFS，可以用 Tarjan 缩掉那个环，不容易错。（AT_abc357_e）
• 基环树看成一个环上挂了一堆树。
• 最优化问题考虑能不能转为最短路。
• 有一个量数据范围特别小，考虑分层图。
• 图上走 $k$ 步，考虑矩阵快速幂。
• 平面图
  • 平面图是稀疏图。（$m \le 3n-6$）
  • 平面图转对偶图。
    • 网格图是特殊的平面图。

博弈论

• 人为制造部分分。

数学

基础

• 警钟撅响 log10 等浮点数函数在 long long 范围内会有精度误差（ABC357D）
• 警钟撅响 等比数列求和特判公比为 $1$（P4948）
• 没思路时打表。

排列组合

• $\binom n m \times \frac {n-m} {m+1} = \binom n {m+1}$，可以 $\Theta(m)$ 计算 $\binom n m$，适用于 $n$ 巨大的情况。
  • 优秀的实现
• 计算二项式系数不要只想着 $\frac {n!} {m! (n-m)!}$，数据范围小的时候可以杨辉三角。

数论

• 不一定要推神秘柿子，可能只是个 DP。
• 出现 $\sum\limits_{i} f(\gcd(i,n))$，转成枚举 $\gcd$。
• 拆 $d(nm)$ 这样的结构时，因为积性函数所以令 $n=p^a, m=p^b$，然后再推。
• 矩阵也可 BSGS。（P3306）
• 单位根反演。
  • $[2 \nmid n] = \frac {1^n - (-1)^n} 2$。
• $\nu_p(n!) = \frac {n - s_p(n)} {p-1}$，其中 $s_p(n)$ 表示 $n$ 在 $p$ 进制下的数位之和。
  • $\nu_2(n!) = n - \text{popcount}(n)$。
• Vandermonde determinant $\prod\limits_{i<j} (a_i - a_j)$ 的计算
  • $a$ 的值域较小时，直接对着值域数组 FFT，$O(V \log V)$。
  • $a$ 的值域较大时，似乎有基于多项式多点求值的解法，$O(n \log^3 n)$。

字符串

• 首先考虑 Hash。
  • 很多自动机题都可以通过哈希在多 1log 的时间复杂度内解决。
  • 二分哈希可以 1log 比较两字符串字典序。

• **PL：若 $p,q$ 为 $S$ 的周期且 $p + q - \gcd(p,q) \le

  S

  $，则 $\gcd(p,q)$ 也为 $S$ 的周期。**

  • 推论：一个字符串的所有整周期对 $\gcd$ 封闭。
  • 推论：一个字符串的所有整周期都是其最小整周期的倍数。

  • 推论：**若 $S$ 的最小整周期不是 $

    S

    $，则最小整周期等于最小周期。**

• 括号匹配首先应当考虑匹配栈。
  • 可以考虑矩阵 Hash。（P9753）
• 回文串问题枚举对称轴然后二分。
• 自动机上也可以做 DP。
  • 作为图上 DP，在数据范围较小时可以考虑矩阵加速。（P3193）

计算几何

• 警钟撅响 与直线有关的计算几何题，特判点数 $n=1$。（P1142）
• 考虑随机旋转人类智慧。（P1429）

计算几何（假）

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

其它

• 警钟撅响 使用 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$。
  • 若 $\gcd(a,b) = a \oplus b$，则 $a - b = a \oplus b = \gcd(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(\log n)$ 的。
  • 考虑随机化。（P3765）
• $(-1)^n = 1 - 2n + 4 \left\lfloor \frac n 2 \right\rfloor$。