summary-skills

Table of Contents

优化运行效率

时间

值域线段树查询某段值域的元素个数时, 如果当前结点下没有元素, 返回 0 (主席树同理).

费用流中, 对于连向汇点的边, 不添加其对应的反向弧.

1e6 级别的数据范围, 如若不开 O2 优化, 手写二分的效率会明显高于 lower_bound.

LCT 中, 宏定义的 isroot 效率明显高于函数.

单点问题 SMT 可考虑自底向上.

高维 DP 将相同的维度优化掉可以减小空间开销. (定义指向二维数组的指针: int (*it)[MAXN] )

输入为实数 的题, 在有条件的情况下, 可将 long double 换为 long long (将所有的数乘上一个很大的数) 可以卡常.

逆序对问题虽然可以 discrete + sort + BIT 来解决, 但效率远低于 归并排序.

高维DP 可以通过优化掉不可能使最终答案更优的状态使得总方案数大大减小. 如 CF 739E, \(O(n^3)\) DP大力优化状态数后最坏情况也只需 2s (O2)

定义 \(U\) 为 \(N\) 位二进制下所有数字的集合. 显然, \(|U| = 2^{N}\). 设 \(S\) 为 \(U\) 的任意一个子集, 已预处理出数组 \(g(S)\), 现在要求构造 \(f(S) = \sum_{S_0 \subseteq S} g(S)\), 暴力枚举子集复杂度肯定是 \(O(3^{N})\) 的. 但是我们可以通过优化做到 \(O(N\times 2^{N})\). 详情戳这里.

只使用位运算 (如线性基) 时可以用 BITSET.

假定要求组合数 \(\binom{n}{m}\), 即使 \(n\) 很大, 如果 \(m\) 比较小, 依然可以 \(O(m)\) 计算. 注意这一点.

计算结果很大时应考虑结合题意在模意义下做.

空间

bool 数组如使用 bitset, 空间理论上只有原来的 \(\frac{1}{8}\). 但是无 O2 优化时会有明显的时间效率差异.

线性筛卡空间时, mu 可以开成 bool (特判一下即可) 或 char; 存素数的数组不必开到 MAXN 级别.

简化程序

点分治在有条件的情况下, 建议在 dfs 出当前子树的同时记录 dfs序, 这样每一种操作都是一个 for 循环而非一个 dfs函数.

合理运用 std::for_each (from _debug) 和仿函数 (必要时可以用 template ) 以简化代码. 前者有利于进行简单的序列操作, 后者在某些数据结构上很有效果. (静态线段树, 块状数组)

重载 [] 运算符, 在某些时候是行之有效的. 这能配合 struct/class 发挥出强大的威力. 主要用于简化访问数据结构中的元素的过程.

带回溯的搜索由于往往会用全局变量记录当前搜索到的状态, 当回溯不好写时, 不妨开数组存下所有的状态, 回溯的时候粘贴回去即可.

算法实现

对于容斥题, 如果能够设计出可以容斥的状态却对如何容斥无法下手, 可以尝试用减法转移状态.

调试程序

大数据是必要的.

小数据可以手动构造一些, 然后手算验证算法的正确性.

宜手动造一些答案显然的大数据, 验证正确性.

多组数据时造的数据也应多组.

HOME