训练计划第四周

二分

模板： 当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。

int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。

int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

视频讲解：https://www.bilibili.com/video/BV1s34y1d7Kj?share_source=copy_web

题单：

​ https://www.luogu.com.cn/problem/P2249（模板题必写）

​ https://www.luogu.com.cn/training/111#information

​ http://120.78.128.11/Challenge.jsp#B11

​

贪心

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

总的来说贪心就是一种思维，思路，多刷题就能悟道，虽然但是贪心只有在做贪心的时候才是对的。

题单：http://120.78.128.11/Challenge.jsp#B5（看一下他的模块说明把第一题做了）

​ https://www.luogu.com.cn/training/110#problems

要求

老样子一周至少8道题目，二分要刷到你把板子背下来为止，不一定非得是我这个板子，贪心就是一种思维你理解思维多刷题就可以了，然后没事练练思维题。