考前警示后人

综合

• 多测记得清空。
• 开 long long。
• 注意开了 long long 时，printf 的格式符要用 %lld。同理，double 也要 %lf。
• 用 cin/cout 时一定要 ios::sync_with_stdio(0)，否则很慢！调代码的时候建议删掉，但最终代码一定要有。注意加了之后输入输出只能用 cin 和 cout。
• 好好检查 freopen 是否写错。
• ios::sync_with_stdio(0) 时不要写 fclose。
• 不要出现拼写错误。如 itn main()，int mian()。
• 万能头是 bits/stdc++.h！不要打成 bits\stdc++.h！Windows 下这样没有问题，但是 Linux 下会 CE。最好把所有代码放 Linux 下跑一下样例。
• 同理，有一些其它变量名也是只有 Linux 下会 CE，如 kill。
• 引用了 cmath 头文件时不能定义全局变量 j0，j1，y0，y1！特别是 y1，每年都有无数人中枪！
• 还有，next，time，pipe，log，pow10 也不能做全局变量名！一个很好的解决方法：只用英文单词的辅音字母，或者干脆中文拼音。
• #define 一定要加括号！如 #define f(x) x*x 之后，f(2)+f(2) 会展开成 2*2+2*2，f(1+1) 会展开成 1+1*1+1。正确的写法是 #define f(x) ((x*x)*(x*x))。
• abs 函数返回值是 int。不要 abs(long long) 或 abs(__int128)。
• int 左移超过 $31$，long long 左移超过 $63$ 都是 UB。
• 最后，算清复杂度，别瞎写超时了。

DP

• 转移时记得取模，模数不要写错。
• 如果需要，记得 memset 整个数组为正无穷或负无穷。不要漏写或写错边界条件。memset 成负无穷时注意不要 0xcf，建议 -0x3f（当然 0xc0 也是对的）。
• 想清楚转移方程是否正确，最好证出来，证不出来也要拍出来。
• 如果想到了复杂度并不正确的 DP，不要放弃这个思路，也许可以优化。
• 树形 DP 有时要特判叶子节点。
• 算好空间。一般来说，滚动数组能开就开，压维能压就压。
• 记得特判无解。

数据结构

• 空间要开够。线段树 $4$ 倍空间，主席树 $Q \log N$。
• 注意不要 pushup 或者 pushdown 叶子节点。
• 标记下传记得处理多个标记叠加。
• max 和 min 不要 #define。
  为什么我要选择在这里说这个？因为数据结构里面这个错误被坑的最惨。在 #define 时，如果传入的两个参数是函数，那么会发现，所有函数都被调用了两次。
  比如下面的代码你会发现被卡到了 $O(n)$。
  CPP

  #define max(x,y) ((x)>(y)?(x):(y))
  int query(int u,int l,int r)
  {
  	if(l>tr[u].l||r<tr[u].r) return -2147483647;
  	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
  	int m=(tr[u].l+tr[u].r)/2;
  	pushdown(u);
  	return max(query(u*2,l,r),query(u*2+1,l,r));
  }
  

  事实上，max 和 min 你都不需要手写，自带的已经可以了，手写卡常效果也并不明显。
• ST 表要预处理 log。
• 还有并查集要注意合并的是祖先而不是结点本身。
  错误：
  CPP

  fa[x]=y;
  

  正确：
  CPP

  fa[find(x)]=find(y);
  

图论

• 看清有向图无向图。
• 无向图空间要开够。
• 建虚点的话，点权数组空间也要开够。
• 最短路注意有没有负边权，有的话要用 SPFA。记得判负环。
• 注意最短路初始化距离数组为正无穷。
• 欧拉路要特判回路。
• Floyd 三层循环顺序是 k，i，j。
• 拓扑排序需要满足是有向无环图。
• 网络流记得建反边，正反边要挨在一起建，反边边权为 $0$。最小割不能割掉的边边权为正无穷。
• 树上 DFS 记得不要从儿子 DFS 回父亲。
• 树剖链修改或链查询记得是 if(dep[top[x]]<dep[top[y]]) swap(x,y); 而不是 if(dep[x]<dep[y]) swap(x,y)。

字符串

• Trie 空间要开够。
• KMP 求 border 时要注意，border 降到 $0$ 的时候就不要再向后找了，否则会死循环。
• 后缀排序注意不要数组越界。

数学

• 组合数学中求 $C^m_n$ 要特判 $n<m$ 返回 $0$。
• 预处理阶乘算组合数时要注意 $0!=1$。
• 矩阵乘法要检查好递推式再写。
• 中国剩余定理要求所有模数互质。如果不互质请使用扩展中国剩余定理。
• 快速幂如果模数平方爆 long long 要写快速乘法。注意此时快速幂复杂度为 $O(\log^2 n)$。

STL

• 定义超过 $3 \times 10^5$ 个 queue/stack/deque 基本上一定会爆空间。
• map 常数很大，一般来说数据规模到 $10^6$ 就可以放弃了。
• bitset 在卡常时建议手写。
• vector 的 insert 和 erase 是 $O(\sqrt n)$。
• map 系列和 set 系列是 $O(\log n)$ 的。特别地，别用 unordered_map，会被卡。
• map 判断是否存了一个数的时候要用 mp.count(x)，而不是 mp[x]（因为可能存了 $0$ 你却当没有）。
• set 中 lower_bound 要用 s.lower_bound(x)。upper_bound 同理。
• 还有 set 重载小于号的时候要写上所有关键字。去重的标准是 !(a<b||b<a)。
  错误：
  CPP

  struct node
  {
  	int fi,se;
  };
  bool operator<(node x,node y)
  {
  	return x.fi<y.fi;
  }
  

  正确：
  CPP

  struct node
  {
  	int fi,se;
  };
  bool operator<(node x,node y)
  {
  	return x.fi!=y.fi?x.fi<y.fi:x.se<y.se;
  }
  

• multiset 删一个用 s.erase(s.find(x))，删全部用 s.erase(x)。
• 还有：打暴力时不要测大样例时让 STL 容器里面太多东西，否则电脑极有可能会蓝屏。别问我怎么知道的。

• 别冒险打暴戾语言，小心禁赛。