—— 简单题不 sb 是什么水平?

—— 国家队水平。

sb 错误

  • 开 long long 时记得快读也要开 long long。

  • 记得删调试信息,尤其是 cerr。

  • 多测时要小心使用 memset。

  • operator 前面记得加返回值类型名。(dev c++ 不报错不警告)

  • 跑的很快可能是因为被优化了,因此不要用空循环测运行用时。

  • (用于在线比赛)RE 可能是爆栈了。

  • 不要假根号分治(可能大于 / 小于根号的同样可以处理小于 / 大于根号的)。

  • 对常数有要求时应尽可能地避免复杂度瓶颈上的 push_back/emplace_back,解决方法有:在 push_backreserve、使用 resize、使用传统数组等。

  • for (auto element : container) 需要在原处修改时使用 auto & 而非 auto

  • 不要同时 vector<...> a(...)a.push_back(...) 而导致数组长度翻倍且前一半是空的。

  • q=0 不一定是不输出,例如题目要求输出答案的异或和时,就要输出 0。

  • OI 赛制记得自己测极限数据(最大 & 最小)。

  • 不要把动态开点线段树写成可持久化线段树(常数会大)。

  • 无符号整型(如 container.size())减去一个正数时需要留意,若不能保证结果非负,则需要将无符号整型显式转换为有符号整型再进行运算。

sb 想不到

  • 计数 → 什么是重复的,什么是相同的。要做到不重不漏

  • 最优化 → 什么是不优的,什么是不劣的。

  • 要是怎么样就好了 → 能不能转化成这样。

  • 存在反例 → 反例能否特殊处理。

  • 只用管大小而不关心具体值 → 从小到大、从大到小考虑 / 二分答案转成 01。

  • 构造最小值 → 找到一个较紧的下界,构造出下界(或者构造出一个方案,证明它是下界)。

  • 多次二分时想一想能不能用双指针。

  • 成双成对的元素,在一起怎么样,不在一起怎么样,经常可以用随机数异或来处理。

  • 把整个序列分成若干段,每段求一个值再加起来求最值,暴力是 DP,经常可以用决策单调性优化。

  • 图论相关问题(包括树上问题)可以考虑点和边互相转化。

  • 能够卷积时想一想能不能直接背包。

  • 求生成函数然后带值进去求答案,可以过程中直接算点值。

  • 无法继续优化往往是因为求了不必要的东西。

  • 路径加单点求值可以树上差分 + 树状数组,不需要树剖/LCT。

  • 不要使用动态开点线段树来求不带修的区间和,在对常数有要求时也不要使用 map,而应使用 vector + 二分 + 前缀和。

  • 多次求矩阵快速幂乘一个向量时,可以预处理矩阵的幂(一次,二次,四次,八次…),然后每次都用矩阵乘向量(从右向左依次算),这样预处理复杂度是 $O(n^3\log k)$,单次询问复杂度是 $O(n^2\log k)$。更一般地,求多个矩阵(每个矩阵都是已知的)的积乘上一个向量时,可以利用结合律每次都用矩阵乘向量。