训练计划第四周

二分

模板: 当我们将区间[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道题目,二分要刷到你把板子背下来为止,不一定非得是我这个板子,贪心就是一种思维你理解思维多刷题就可以了,然后没事练练思维题。

0 comments

No comments so far...