蓝桥杯 Python B组 省一必备知识清单

2022 年���赛：我估计 48.5 分左右 (满分 150)。广东总共 78 个省一，我只排到了第 33 (42.3%)

2022 年国赛：最后一道大题没时间写 —— 暴力就能满分的题，血亏，最后国三

2023 年省赛：居然是全省第二 (广东 B 组省一共 91 人，前 2.1%)，差点没把我笑***

2023 年国赛：倒数第二题交的时候多了一个 print，只拿了国二

在本篇文章中，我将从“知识预备”、“刷题网站”、“函数模板”三个方面为大家讲解怎样准备蓝桥杯 Python 组的比赛

知识预备

开发环境

官方要求的是 IDLE，但是就 2023 年来说，是可以用 PyCharm 的 (具体还是要找组委会问清楚)

用 PyCharm 的话自己配好 3.8.6 的环境就可以 (我个人用的是 3.8.0，不建议 3.8.0 以下，版本对 math 库的一些函数影响有点大，可能会导致报错)

可以使用以下代码查看自己的 Python 版本

import sysprint(sys.version_info[:3])

以下是 PyCharm 和 IDLE 常用的快捷键

如果使用 IDLE 的话，可以通过以下方法来打开代码提示 (假设 Python 的安装路径为 ~)：

• ~/Lib/idlelib/autocomplete.py：import
  • ~/Lib/idlelib/config-extensions.def：popupwait= 0

    算法知识

    具体考点可以看这篇文章： 

    蓝桥杯大赛软件类备赛指南https://blog.csdn.net/weixin_43914593/article/details/128296251我主要看了这个网课的前 40 集，因为专业课学了树、图，所以重点放在了动态规划、背包、状态压缩、线段树

    【蓝桥杯比赛】视频教程（入门学习+算法辅导）https://www.bilibili.com/video/BV1Lb4y1k7K3?

    贪心算法的话，比较玄学，练习为主：LeetCode：贪心算法题集

    Python 组和其它组的不同点在于，代码简洁在很多情况下约等于高效，例如：

    • 求一个列表的最大值及其索引时，暴力的 max + index 比 for 循环更快
    • 使用 class 写的线段树减少运算量时，运行时间反倒比暴力写法还长 (也有可能是我的类写得太烂)

      所以在准备 Python 组的比赛时，一些算法是不需要学的。同时，因为 Python 的效率并不是和运算量直接挂钩，所以还要多对比不同写法所花费的时间：

      import mathclass timer:    def __init__(self, repeat: int = 1, avg: bool = True):        self.repeat = max(1, int(repeat) if isinstance(repeat, float) else repeat)        self.avg = avg    def __call__(self, func):        import time        def handler(*args, **kwargs):            t0 = time.time()            for i in range(self.repeat): func(*args, **kwargs)            cost = (time.time() - t0) * 1e3            return cost / self.repeat if self.avg else cost        return handler# 求 x! 关于 1398173074 的余数mod = 1398173074@timer(repeat=2)def fun1(x):    return math.factorial(x) % mod@timer(repeat=10)def fun2(x):    result = 1    for i in range(2, x + 1):        result = result * i % mod    return resultfor f in [fun1, fun2]:    print(f'Cost:\t{f(540880):.2f}\tms')

      Cost:    3238.52    ms

      Cost:    91.90        ms

      对于 ，Python 1 秒内可以进行 8e7 次运算 (加法亦然)

      比赛中题目的测评时间一般是 10 s 以上 (甚至有 30 s)，解题时根据问题规模设计好代码的时间复杂度

      然后比赛答题时，一定要过一遍整份考题，因为题目的难度不一定是递增的 —— 要知道我 22 年国赛看见全卷最简单的题在最后、分值最高、还没时间做有多绝望

      标准库

      学标准库之前，首先还得会 Python 的一些基础数据类型：str、list、tuple、dict、set

      还有文件相关的操作，填空题可能会碰到需要读取 .txt 的题目，运气不好的话碰到超长文本的是复制不了的 (超出剪切板长度限制)

      而且对于类和实例的认识是越深越好 (如类似 __call__ 这种名字的类方法)，这有利于你直接阅读源代码，提高对标准库的认知

      一般情况下，标准库函数的性能是最好的，所以能用一定要用 (除了以下的必修库之外，pathlib.Path 也是很值得了解的)

      如果不知道以下的这些代码怎么用，可以在我的主页搜索相关代码，就可以看到相应的例题

      如果在考试过程中忘记了某个函数的用法，可以使用 help 函数查看说明文档

      bisect

      对于有序数列，二分法查找的速度会快很多

      升序	bisect_left(array, x)	二分法查找x	已有x时 → x位置
      bisect(array, x)	已有x时 → x右侧
      insort(array, x)	二分法插入x

      cmath

      数值操作：
      pi	п	isnan(z)	判断nan	isinf(z)	判断inf	isfinite(z)	是否有限
      tau	2п	nan	nan	inf	∞	isclose(a, b)	是否相近

      cmath 库是复数运算库，在蓝桥杯比赛里面很实用

      蓝桥杯经常出现一些 x-y 坐标系求两点间距离、角度的题，利用复数的模、相角求解可以简化代码和提高运算速度

      属性访问：
      z.real	复数实部
      z.imag	复数虚部
      z.conjugate()	对应共轭复数
      abs(z)	复数的模
      phase(z)	复数相角 (-п, п]
      rect(r, phi)	极坐标 → 复数
      polar(z)	复数 → 极坐标 (r, φ)

      运算函数：
      sqrt(z) / isqrt(z)	z ^ 0.5	pow(z, a)	z ^ a
      sin(z) / cos(z) / tan(z)	三角函数	正运算
      asin(z) / acos(z) / atan(z)	逆运算
      exp(z) / log(z, base=e)	指数运算

      collections

      Counter 可快速统计序列 (如字符串) 中的元素，而 deque 优化了队列端点的相关操作 (还可以自动限定长度)

      计数器：
      Counter(var / **kwargs)	实例化计数器
      实例方法	elements()	返回元素迭代器
      most_common(int)	返回指定数量高频值
      update(var)	更新计数器	加法
      subtract(var)	减法

      队列：
      deque(iter, maxlen)	实例化限长队列
      实例方法	append / appendleft(obj)	入队
      extend / extendleft(iter)	迭代入队
      pop / popleft()	出队
      insert(i, obj)	将元素放在位置i
      count(obj)	返回元素出现次数
      index(obj, start, end)	返回元素的位置

      copy

      主要是 deepcopy 比较有用，特别是对于维度大于 1 的 list、多重 dict 的 copy

      copy(obj)	浅拷贝变量
      deepcopy(obj)	深拷贝变量

      datetime

      蓝桥杯有时会有一些关于日期的题，这个库配合 try - except 语句可以判断某个日期的合法性

      time 库的话就没什么必要了，不如这个库快捷；了解下 time 库的浮点型秒数、strptime 方法就可以

      日期：
      datetime(year, month, day, hour=0, minute=0)	实例化日期
      类方法	today()	当前日期
      fromtimestamp(t)	秒数 → 日期
      strptime(date_string, format)	字符串 → 日期
      实例方法	date()	返回日期实例
      time()	返回时间实例
      weekday()	返回0 ~ 6 (Mon ~ Sun)
      timetuple()	返回时间元组
      timestamp()	返回秒数
      replace(year, month, day, hour, minute)	更新日期

      两个 datetime 实例 (日期) 相减可以得到 timedelta 实例 (时间差)

      时间差：
      timedelta(days, seconds, minutes, hours, weeks)	实例化时间差 同类可加减比较，可与int乘除
      实例属性	days	天数
      seconds	秒数

      functools

      lru_cache 用于记忆化 DFS 时，可以自动存储函数在不同参数下的运行结果，效率比自己写的 dict 快很多

      partial(func, *args, **kwargs)	返回部分应用给定参数的函数
      lru_cache(maxsize)	返回结果缓存修饰器 (记忆化DFS神器)

      heapq

      堆在解决“前 n 大”、“前 n 小”的问题上有很高的效率

      这个库只提供了小根堆的函数 (大根堆都是隐藏函数)，要使用大根堆的话对所有元素取负就行了

      小根堆：
      heapify(list)	原地小根堆化
      heappush(heap, item)	添加堆结点
      heappop(heap)	弹出堆顶，并重排
      merge(*sorted, key, reverse)	合并有序数列
      nsmallest(n, iter, key)	返回升序前n元素
      nlargest(n, iter, key)	返回降序前n元素
      heapreplace(heap, item)	pop → push
      heappushpop(heap, item)	push → pop

      heapq 不仅可以针对数值类型，还可以用于有 __lt__ 方法的自定义类

      itertools

      迭代工具库封装了一些迭代操作 (虽然实现的功能很简单，但是很快)

      运算：
      accumulate(iter, operator)	返回前缀和
      groupby(iter, key)	返回分组结果 (dict)
      permutations(iter, k)	返回全排列
      combinations(iter, k)	返回全组合	元素无重复
      combinations_with_replacement(iter, k)	元素有重复

      过滤：
      compress(iter, bool_seq)	返回压缩过滤序列
      takewhile(filter, iter)	筛选满足条件的值	while - break
      dropwhile(filter, iter)	滤除满足条件的值

      迭代器：
      product(*iter)	返回笛卡尔积
      islice(iter, start, stop, step)	返回切片迭代器
      chain(*iter)	返回级联迭代器
      cycle(iter)	返回循环迭代器	级联迭代器
      repeat(obj, times)	重复元素

      math

      数值操作：
      pi	п	isnan(x)	判断nan	isinf(x)	判断inf	isfinite(x)	是否有限
      tau	2п	nan	nan	inf	∞	isclose(a, b)	是否相近

      开方的速度：math.isqrt 函数 (取整) > math.sqrt 函数 > 运算符

      求幂的速度：

      • 取整：运算符 > pow 函数 > int(math.pow) > 自编二分快速幂 (无取模)
      • 无取整：math.pow > 运算符 > pow 函数 > 自编二分快速幂 (无取模)
      • 取模：pow 函数 > 自编二分快速幂

        当用到取模的幂运算时，只有内置的 pow 函数提供了 “mod” 参数，math.pow 则没有

        运算函数：
        sqrt(x) / isqrt(x)	x ^ 0.5	pow(x, a)	x ^ a
        factorial(x)	x!	prod(iter)	累乘
        perm(n, k)	排列数，P = n! / (n - k)!
        comb(n, k)	组合数，C = P / k!
        sin(x) / cos(x) / tan(x)	三角函数	正运算
        asin(x) / acos(x) / atan(x)	逆运算
        exp(x) / log(x, base=e)	指数运算
        ceil(x) / floor(x)	取整
        degrees(x) / radians(x)	弧度  角度
        dist(p, q)	欧式距离	点 → 点
        hypot(*coord)	点 → 原点
        gcd(a, b) / lcm(*int)	最大公约数 / 最小公倍数

        其中的 lcm 只有在 Python 3.9.0 以上才可以用，而 gcd 的用法也在 Python 3.9.0 更新为 gcd(*int)，可以求解多个整数的最大公约数。准备一个 Python 3.9.0 可以在填空题省下不少功夫

        re

        我觉得这是个必学的库，在字符串的处理上有很高的效率

        会这个的话考试碰上乱杀 (比如 22 年国赛的内存管理)，不会的话等着被乱杀

        正则表达式：
        .	换行符之外的任意字符
        \d	数字 (\D表非)
        \s	空白符 (\S表非)
        \w	字母、数字、下划线、汉字 (\W表非)
        ^	置于开头，只匹配前缀
        $	置于结尾，只匹配后缀
        |	或
        ( )	捕获组 (findall有效 / .group(1)读取)
        [ ]	字符类	-	在中间则表范围 (\u4e00-\u9fa5表中文)
        ^	在首位表不在其中的字符
        { }	数字 / 范围表前一字符重复次数
        *	等价 {0,}	+	等价 {1,}	?	等价 {0,1}

        编译标志RegexFlag：
        I	忽略字母大小写	M	'^'、'$'跨行匹配
        S	'.'可匹配换行符	X	忽略表达式中的空格和注释

        匹配函数：
        compile(pattern, flags)	返回编译的正则表达式
        findall(pattern, string, flags)	返回匹配的字符串列表
        sub(pattern, repl, string, count, flags)	替换子字符串
        split(pattern, string, maxsplit, flags)	分割字符串

        匹配实例：
        search(pattern, string, flags)	返回匹配结果
        match(pattern, string, flags)	返回前缀的匹配结果
        finditer(pattern, string, flags)	返回所有的匹配结果
        实例方法	group(i=0) / groups()	匹配内容
        start(i=0)	起始位置
        end(i=0)	结束位置
        span(i=0)	匹配范围

        刷题网站

        经过 2022 的省赛国赛，还是得说：要相信 Python 暴力算法的力量

        在刷题的时候，要把有价值的题目记录下来 (e.g. 写博客)，方便日后复习

        如果没时间记录的话，可以跟着我的 数据结构与算法专栏 练习、复习

        蓝桥杯练习系统

        网站链接：http://lx.lanqiao.cn/problemsets.page

        “基础练习”里面虽然都是无脑题，但是还是得刷一下的，主要是了解蓝桥杯的测评方法

        然后刷题以“历届试题”为主，但是这份题不太全面，建议在 CSDN 上找别人的题解跟着练

        我自己在准备蓝桥杯的时候也写了不少题解，可以看我的专栏：数据结构与算法专栏

        力扣

        网站链接：https://leetcode.cn/problemset/all

        力扣的题型和蓝桥杯真题的题型很不一样 (主刷力扣 = 完蛋)，但是力扣有很多的优点：

        • 测评透明度高：哪个样例没通过可以看得清清楚楚，会提升你对特例的认知
        • 性能排名：力扣会把你的代码性能和其它用户做比较，可以提升代码性能优化能力
        • 题解全面：评论区有官方、民间题解，有多个解法的性能比较

          我写的题集涉及到了较多的数据结构，这些在蓝桥杯测评系统、C 语言网是学不到的

          有些题目比较简单，可以选择性地刷一些：LeetCode：算法面试题汇总

          C 语言网

          网站链接：https://www.dotcpp.com/oj/lanqiao/

          C 语言网的题集收录了蓝桥杯的考试真题，而且比较全面，强力推荐

          但是 C 语言网 Python 版本比较低 (3.8 以下)，不支持 math 库的一些函数 (如 isqrt)

          函数模板

          考试是不能带模板的，而且绝大多数时候都是不能直接套用的 (需要根据题目微改)，所以建议理解构造思路，自己多默写 (标 * 的表示重要性较低)

          排列组合

          字典序算法

          以 [8, 3, 7, 6, 5, 4, 2, 1] 为例，这个函数完成的工作就是：

          • 从右到左开始查找，因为 3
          • 从右到左开始查找比 3 大的数，得到 4 的索引记为 right
          • 交换 left 和 right 对应的数，此时序列变为 [8, 4, 7, 6, 5, 3, 2, 1]
          • 可以看到 left 右侧全是逆序的 (即 4 的右侧)，所以逆转 seq[left + 1: ] 得到 [8, 4, 1, 2, 3, 5, 6, 7]

            def next_perm(seq):    ''' 找到下个字典序        e.g.: 8 3 7 6 5 4 2 1                |       |    '''    n = len(seq)    filt1 = lambda i: seq[i] >= seq[i + 1]    try:        l = next(it.dropwhile(filt1, range(n - 2, -1, -1)))        # 找到交换位        filt2 = lambda r: seq[l] >= seq[r]        r = next(it.dropwhile(filt2, range(n - 1, l, -1)))        seq[l], seq[r] = seq[r], seq[l]        # 逆转逆序区        seq[l + 1:] = reversed(seq[l + 1:])        return seq    except StopIteration:        return None

            数论

            前 n 项平方和：

            最小公倍数：

            费马小定理： (p 为质数，a 不是 p 的倍数)

            乘法逆元： (a, p 互质)

            裴蜀定理：

            大于 3 的质数可被表示成 

            质数筛法

            网上比较推荐的算法是欧拉筛 (线性复杂度，无重复枚举) 和埃氏筛 (有重复枚举)，但是在 Python 代码中，代码较为简单的埃氏筛有更高的效率

            def prime_filter(n):    ''' 质数筛选 (埃氏筛法)        :return: 质数标志        :example:        >>> is_prime = prime_filter(10000)        >>> is_prime[2:].count(True)        1229'''    is_prime = [True] * (n + 1)    # 枚举 [2, sqrt(n)]    for i in range(2, math.isqrt(n) + 1):        if is_prime[i]:            for c in range(i ** 2, n + 1, i):                is_prime[c] = False    return is_prime

            质因数分解

            试除法是最基本的分解方法，在 Python 中 Pollard rho 算法对 7e5 以上的大数分解更快：大数的质因数分解 Python

            def try_p(n, factor={}):    ''' 试除法分解'''    i, bound = 2, math.isqrt(n)    while i  1: factor[n] = 1    return factor

            所有因数

            def all_factor(n):    ''' 所有因数'''    prime = try_p(n)    factor = [1]    for i in prime:        tmp = []        for p in map(lambda x: i ** x, range(1, prime[i] + 1)):            tmp += [p * j for j in factor]        factor += tmp    return factor

            中国剩余定理 *

            求满足以下条件的数 (其中  为质数)：

             可被除了  以外的模数整除，根据费马小定理 ，有以下推导：

             可被除了  以外的模数整除，同时满足 

             可看作一个余数单元， 即可满足上述不等式组的第 i 个条件 ，而不增加其它模数下的余数

            将每个余数单元乘以对应的余数累加起来，便可得到满足条件的数的余数项：

            def rem_theorem(mods, rems, lcm_fcn=math.prod):    ''' 中国剩余定理        :param mods: 模数集        :param rems: 余数集        :param lcm_fcn: 最小公倍数的求解函数 (模数集全为质数时使用 math.prod)        :return: 满足给定条件的余数项'''    lcm = lcm_fcn(mods)    # 费马小定理求逆元, 要求 a,p 互质    inv = lambda a, p: pow(a, p - 2, p)    result = 0    for p, r in zip(mods, rems):        a = lcm // p        result += r * a * inv(a, p)    return result % lcm

            在用这个函数的时候一定要注意模数集的规模，因为是累乘所以数位会暴增，这会大幅度影响运行耗时

            图论

            单源最短路

            Dijkstra：使用额外的空间记录“单源最短路”，主体使用 while 循环

            def dijkstra(source, adj):    ''' 单源最短路径 (不带负权)        :param source: 源点        :param adj: 图的邻接表'''    n = len(adj)    # 记录单源最短路, 未访问标记    info = [[float('inf'), True] for _ in range(n)]    info[source][0] = 0    # 记录未完成搜索的点 (优先队列)    undone = [(0, source)]    while undone:        # 找到离源点最近的点作为中间点 m        m = heapq.heappop(undone)[1]        if info[m][1]:            info[m][1] = False            # 更新单源最短路            for i in filter(lambda j: info[j][1], adj[m]):                tmp = info[m][0] + adj[m][i]                if info[i][0] > tmp:                    info[i][0] = tmp                    heapq.heappush(undone, (tmp, i))    return info

            SPFA：使用额外的空间记录“单源最短路”、“顶点队列”、“在队标记”、“入队次数”，主体使用 while 循环 (队列非空)

            def spfa(source, adj):    ''' 单源最短路径 (带负权)        :param source: 源点        :param adj: 图的邻接表'''    n, undone = len(adj), [(0, source)]    # 单源最短路, 是否在队, 入队次数    info = [[float('inf'), False, 0] for _ in range(n)]    info[source][0] = 0    while undone:        # 队列: 弹出中间点        m = heapq.heappop(undone)[1]        info[m][1] = False        # 更新单源最短路        for i in adj[m]:            tmp = info[m][0] + adj[m][i]            if info[i][0] > tmp:                cnt = info[i][-1]                # 入队: 被更新点                if not info[i][1]:                    cnt += 1                    heapq.heappush(undone, (tmp, i))                    # 终止: 存在负环                    if cnt > n: return False                info[i] = [tmp, True, cnt]    return info

            多源最短路

            def floyd(adj):    ''' 多源最短路径 (带负权)        :param adj: 图的邻接矩阵'''    # import itertools as it    n = len(adj)    for m in range(n):        for i, j in it.combinations(it.chain(range(m), range(m + 1, n)), 2):            adj[i][j] = min(adj[i][j], adj[i][m] + adj[m][j])

            拓扑排序

            def topo_sort(in_degree, adj):    ''' AOV 网拓扑排序 (最小字典序)        :param in_degree: 入度表        :param adj: 图的邻接表'''    undone = [i for i, v in enumerate(in_degree) if v == 0]    heapq.heapify(undone)    order = []    while undone:        v = heapq.heappop(undone)        order.append(v)        # 删除该结点, 更新入度表        for i in adj[v]:            in_degree[i] -= 1            if in_degree[i] == 0: heapq.heappush(undone, i)    return order if len(order) == len(in_degree) else False

            最小生成树 *

            def prim(source, adj):    ''' 最小生成树        :param source: 源点        :param adj: 图的邻接表'''    edges, n = [], len(adj)    # 未完成搜索的结点    undone = [(w, i) for i, w in adj[source].items()]    heapq.heapify(undone)    # 和树的最小距离, 最近结点, 未完成标志    info = [[adj[source].get(i, float('inf')), source, True] for i in range(n)]    info[source][-1] = False    while undone:        # 未被选取的顶点中, 离树最近的点        v = heapq.heappop(undone)[1]        if info[v][-1]:            info[v][-1] = False            edges.append((info[v][1], v))            # 更新最近结点            for i in adj[v]:                if info[i][0] > adj[v][i]:                    info[i][:2] = adj[v][i], v                    heapq.heappush(undone, (adj[v][i], i))    return edges

            并查集

            目前我还没有遇见用并查集的题目，有备无患嘛：

            • __init__：写入实例属性，_pre 为前驱结点列表 (初始均为自身)，_rank 为结点级别
            • find：查找某个结点的根结点
            • is_same：检查两个结点是否属于同一棵树
            • join：合并两个结点的根结点，根据根结点级别进行合并
            • __repr__：规定并查集的字符串形式，调试时使用 

              class Disjoint_Set:    ''' 并查集'''    def __init__(self, length):        # 记录前驱结点, 结点级别        self._pre = list(range(length))        self._rank = [1] * length    def find(self, i):        while self._pre[i] != i:            i = self._pre[i]        return i    def is_same(self, i, j):        return self.find(i) == self.find(j)    def join(self, i, j):        i, j = map(self.find, [i, j])        # 前驱不同, 需要合并        if i != j:            # 访问前驱级别            rank_i, rank_j = self._rank[i], self._rank[j]            # 前驱级别相同: 提高一个前驱的级别, 作为根结点            if rank_i == rank_j:                self._rank[i] += 1                self._pre[j] = i            # 前驱级别不同: 级别高的作为根结点            else:                self._pre[j] = i if rank_i > rank_j else j    def __repr__(self):        return str(self._pre)