北京笔记Day1

分治

(略)

复杂度分析

T(n)=2T(n/2)+O(kn)O(knlogn)

CDQ分治

  1. 适用条件:

    1. 离线算法

    2. 每次修改操作对答案贡献独立,操作互不干扰

  2. 简易模型

    计算 [mid+1,r]

    计算 [mid+1,r]

  3. 三维偏序 (a,b,c)

    1. a 属性排序

    2. 用两个指针扫 bibj

    3. 用树状数组维护 c 属性

  4. 例题 (玄学时间)

    1. BZOJ 1176

    2. BZOJ 2716

    3. HDU 5127

    4. Cash

    5. BZOJ 4137

整体二分

  1. 条件:

    1. 答案具有二分性

    2. 修改独立,修改对询问独立

    3. 离线算法

  2. 形如: solve(l,r,S)

  3. 例题:

    1. 静态区间第K小 (主席树)

    2. BZOJ 3110

      1. 线段树套平衡树 (愚蠢的做法)

      2. 权值线段树套线段树

      3. 整体二分

    3. BZOJ 2527

Meet in the middle

  1. 其实就是双向搜索

  2. 例题

    1. 给出一个DAG,求一个点A到另一个点B路径长度为L的方案数

      1. 求出从A和B出发的距离为 L/2 的点及其方案数

      2. ans=集合交集乘积的和

    2. ABCDEF

    3. A

来发评论吧~
Powered By Valine
v1.5.2