二分/分治学习笔记

二分/分治学习笔记

三月 10, 2018

是一篇拖延症晚期拖了好久才开始写的学习笔记

大概记一下关于二分和分治的感想吧

###二分

二分也没啥好说的(况且作为蒟蒻也只会写二分答案),基本套路就是二分答案在检查一下答案,把求值问题转化为判定性问题

值得注意的是:关于限定最大值求最小和限定最小值求最大应当有两种不同的处理

    //限定最小值求最大
    while (l < r){
        mid = l + ((r - l + 1) >> 1);
        if (!check(mid)) r = mid - 1;
        else l = mid;
    }
    return l;
    //限定最大值求最小
    while (l < r){
        mid = l + ((r - l) >> 1);
        if (!check(mid)) l = mid + 1;
        else r = mid;
    }

两者本质的共同点在于:

  1. 当区间长为偶时,一定要将区间平分,否则在区间长足够小的时候会陷入死循环
  2. mid可以满足约束时,一定要将它包含在下一个检查的区间里,否则若mid为解时程序将求不出解

此外:

二分查找配合前缀/后缀和数组进行使用有奇效

###分治

挺广泛的一个操作,包括线段树在内许多东西都是利用的分治的思想.这里记两个印象比较深刻的分治

####二分的分治

经典的就是平面最近点对问题.平面问题反正先离散就是了.接着对x值分成两部分–这是没道理的暴力的分.当分至只有一个点时就得到一个当前最优状态maxint

而分治的核心在于合并操作:整个算法的复杂度就是合并复杂度加上一个logN.对于平面最近点对问题的合并暴力又不失效率:对于割线两边距离不大于当前最优值的点进行配对,查看是否有更优解.(此外除了x值的限定还可以对y值进一步限定).复杂度上看它是一个N^2的合并,但实际上这个"暴力"的算法效率很高

总的来说,如果能写出一个高效的合并,分治可以将一个N降为logN

####快排的分治

这种分治用于求第k大问题等.和其它分治相比,它的特色在于:没有一个固定的mid值,它只有一个随机取的mid的价值,并通过比较这个价值的大小从两边向中间逼近,从而求出mid,用于确定下一个区间.也就是二分的分治的反向操作

当然,由于鄙人比较弱,所以不知道这个操作除了求第k大之外还有什么用