寒假第二次培训 二分 快速幂

Hello_World

比赛链接：寒假第二次培训 二分 快速幂

题单简介

前言

47秒学会二分查找

47秒，我一个双层吉士汉堡都还没吃完，本节的核心思想你就已经学会了！

本节包含二分查找和快速幂两个知识点。同排序一样，algorithm头文件也实现了二分查找的函数upper_bound()、lower_bound()。如果题目不复杂的话你可以直接使用库函数

但有些题目无法直接套这两个函数，需要你结合二分的思想自己实现。自己实现时要注意关于边界条件的思考，如查找大于等于目标值/小于等于目标值的不同情况下，分别要怎么写判断条件？（别小瞧二分查找，理解起来容易，真手写还是有很多坑的。手写二分查找也是我在面试字节实习时遇到过的题）（屠龙者终成恶龙。。。现在我面试别人也出过几次手搓二分的题目）

快速幂的思想和二分比较像。学习完后，尝试弄清楚，如何根据题目数据范围来计算本题在做查找或幂运算时，是否一定需要使用二分查找/快速幂吧！（从时间复杂度角度出发，见练习题1）

学习路线

• 【基础】学习二分查找的基本原理，并学习它的代码实现。
• 【基础】理解二分查找的时间复杂度为什么是O(logn)。
• 【基础】学习lower_bound()和upper_bound()这两个函数的使用方法。

学到这，你就可以完成本节的第2～3题了。

• 【基础】学习快速幂的原理与时间复杂度计算。

学到这，你就可以完成本节的第4～5题了。

• 【提高】学习pow()函数的用法，使用它需要#include，它的计算速度和快速幂一样，一些简单的计算幂的场景可以直接用。当然在本节的题目里，你并不会用得上这个函数。
• 【提高】了解基本的位运算操作，让你的快速幂更快。
• 【提高】学习矩阵快速幂的原理与实现。

需要学习的代码

有的题目里，不能直接使用lower_bound()、upper_bound()，但也需要使用二分的思想才能在规定时间内算出结果。此时需要手写二分的实现框架，并根据题目要求改动。下面提供两个模板（即这两个函数的内部实现原理）。

二分思想的基本实现框架已经很成熟了，你可以直接背下其中一个。做题时，注意模板中>、<、=的关系，可以尝试自己总结一下，什么时候判断条件写>，什么时候写>=？

// 输入参数1: 数组待查找部分的开头地址
// 输入参数2: 数组待查找部分的结束地址
// 输入参数3: 目标值
int* lower_bound(int *begin, int *end, int num) {
    int low = -1;
    int high = end - begin;
    int mid;
    // 这里写大于？还是大于等于？为什么要这么写？思考一下吧！
    while(high - low > 1) {
        mid = (low + high) / 2;
        // 这里写大于？还是大于等于？为什么要这么写？思考一下吧！
        if(begin[mid] >= num) {
            high = mid;
        } else {
            low = mid;
        }
    }
    return begin + high;
}
int* upper_bound(int *begin, int *end, int num) {
    int low = -1;
    int high = end - begin;
    int mid;
    while(high - low > 1) {
        mid = (low + high) / 2;
        if(begin[mid] > num) {
            high = mid;
        } else {
            low = mid;
        }
    }
    return begin + high;
}
const int maxn = 100;
int n = 10;
int a[maxn] = {2, 3, 3, 4, 6, 6, 6, 7, 8, 9};
for(int i = 0; i <= 10; ++i) {
    printf("lower_bound %2d at %2d\n", i, lower_bound(a, a + n, i) - a);
    printf("upper_bound %2d at %2d\n", i, upper_bound(a, a + n, i) - a);
}

资料参考

• 二分查找 视频
• 在网上搜一下upper_bound()、lower_bound()函数的使用方法。
• 快速幂 博客

关于练习题

第4～5题为快速幂，其他均为二分题。请使用本节知识点解决题目，可以尽量使用upper_bound()或lower_bound()函数。

无法直接应用这两个函数要手搓二分时，尽量本地调试完再提交，而不是不断提交不断改。因为比赛时无法实时获取分数，二分的难点不在于理解在于手搓代码后提交一次就能过，练习时可以着重练习一把过的能力。

如果需要使用排序，请使用上节学到的sort()，而不是手搓排序。

《杨辉三角形》这题比较难，21年B组省赛编程大题第三题。如果你当前进度不快，这题可以思考一会后直接看答案（看不懂的话找答疑同学），或者先跳过，等寒假结束后再做。

G01 快速幂，推荐个好记的写法：

typedef long long LL;
const LL MOD = 1000000007;
LL fastPow(LL res, LL n) {
    LL ans;
    for (ans = 1; n != 0; n >>= 1) {
        if ((n & 1) == 1) {
            ans = ans * res % MOD;
        }
        res = res * res % MOD;
    }
    return ans;
}

找素数的3种方法 试除法 埃氏筛 线性筛 动画演示过程 noi大纲数论基础

题目列表

A. T550176 编程小技巧2
B. P2249 【深基13.例1】查找
C. P1678 烦恼的高考志愿
D. P1226 【模板】快速幂
E. P1045 [NOIP 2003 普及组] 麦森数
F. P2759 奇怪的函数
G. P8647 [蓝桥杯 2017 省 AB] 分巧克力
H. P1965 [NOIP 2013 提高组] 转圈游戏
I. P3297 [SDOI2013] 逃考
J. P8749 [蓝桥杯 2021 省 B] 杨辉三角形