跳到主要内容

杂项

本章介绍的是一些难以分类的算法及 OI 相关知识。

双指针

本文将介绍双指针,借同向的滑动窗口与有序数组上的相向逼近,在线性时间内维护区间信息或统计答案。

CDQ 分治

本文将介绍 CDQ 分治,用分治统计前半修改对后半询问的跨区间贡献,解决三维偏序等问题。

整体二分

本文将介绍整体二分,把多个询问的答案一起二分并按贡献分组递归,解决区间第 k 小等问题。

莫队算法

本文将介绍莫队算法,把区间询问按块排序后用双指针离线转移,在 O(n 根号 n) 内求解。

分数规划

本文将介绍 01 分数规划,二分比值后把权值改写为收益减比值乘代价,将分式最优化转为可行性判定。

模拟退火

本文将介绍模拟退火,借降温过程以概率接受劣解跳出局部最优,求解连续无结构的最优化问题。

悬线法

本文将介绍悬线法,逐行递推每条悬线能左右扩展的边界,在 O(nm) 内求最大子矩形。

表达式求值

本文将介绍中缀表达式求值的双栈法与后缀表达式法,并给出以多项式为操作数的完整实现。

主元素问题

本文将介绍主元素问题的求解,包括排序取中位的离线做法与在线的摩尔投票算法。

Kahan 求和

本文将介绍 Kahan 补偿求和,用一个补偿变量记录浮点累加丢失的低位,把总误差压到接近常数级。

珂朵莉树

本文将介绍珂朵莉树,用 set 合并同值区间、以 split 与区间赋值维护随机数据的区间操作。