起飞前检查清单

Social_Zhao · 2020-11-01 19:26:19 · 个人记录

由于这个项目现在是多人合作更新，所以被放在了 Sagari 的博客 上。

这里放我自己的 branch

好吧，对面鸽了。

卡常

1. 求逆元：线性预处理 3\times 10^6 以内的逆元，然后用线性求逆元的式子递归。比快速幂常数小很多。
2. 需要实现同类型的不同功能的数据结构（如单点修改区间查询和区间修改单点查询）两个树状数组，不要整合（写成区间修改区间查询的树状数组）。
3. 压缩重复查询。
4. 不 #define int long long，需要仔细检查 1ll *。
5. 如果 map 不会让复杂度加一个 log 的话就不要用 unordered_map 了。
6. 三目运算符写的 min max 加 inline。
7. 该用 bool 的就不要用 int。
8. 注意有解的奇偶性，可以卡掉一半常数。

数学

线性代数相关

• 高斯消元要消掉所有 j \ne i 的行

字符串

SAM

• 两倍空间

图论

虚树

• key 数组大小 \times 2

圆方树

• 需要修改 / 查询 fa[x] 的时候判根

基环树

• 断环为链时注意 (cir_1, cir_{cnt}) 这一条边

网络流

• tot = 1;

DP

插头DP

• l 和 u 的逻辑运算符写对

斜率优化

• 斜率要乘 1.0
• 注意维护凸壳时的关系符号

计算几何

精度

• 变量用 double
• 比大小用 dcmp
• 绝对值写 fabs

半平面交

• 第一个循环长度是 tot（去重前），第二个是 cnt（去重后）
• 排序 cmp 函数

数据结构

线段树相关

• 线段树 4 倍空间。
• 主席树 30 倍空间。

平衡树

• Reverse 的时候除了要交换信息还要交换左右儿子。

杂项

• 特判 1
• 能光速幂就不要快速幂
• 注意 rand() 值域