【杂谈】我为蓝桥杯做了哪些准备

本人15届蓝桥杯python组国一，并且不是计算机专业科班出身，本科是管科，学习了一些简单的python，硕士跨考金融，也没有进一步进行计算机的学习。比赛前也没进行太多的真题训练，只是在leetcode上练了几个常见算法，准备了一些可能会用到的算法代码，下面分享下我的一些考试经验：

image-20240721162537288

准备考蓝桥杯，一些需要准备且牢记的要点

  1. 注意0，1等边界位置。在各种需要遍历数组的算法中，通常在边界处有不一样的处理方式，尤其要思考在数组最开头能否满足算法要求。

  2. 装饰器@cache可以加速，记录算过的东西，是很好用的减少时间的方法。

  3. 一切皆可发生，多加几个判断不费时间，判断比如输入为空列表，输入为只有1等特殊情况的处理方式。

  4. 蓝桥杯偏向于思维，算法较少。（根据往年经验，dp + 搜索 + 数论 + 枚举 就是所有知识点 ）

  5. 时间复杂度过高，也是可以把代码写上去，得到一部分分数。

  6. 对于特殊值一定要优先考虑，可获得一部分分数。

  7. 没有思路的题，直接暴力枚举，可以获得一部分分数。

一些可能帮到大家的算法集合

排序算法

在蓝桥杯的题型里，它不会让你直接去实现某个算法，而是用一个实际案例中让你使用排序，这样的话，记住一个最好用的nlog(n)的排序算法尤为重要，我记住的就是这个快速排序，当然，如果其他的二路归并等排序算法记住也可以的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def quicksort(nums, low, high):
    if low >= high:
        return
    base = nums[low]
    r = low
    l = high
    
    while r < l:
        while nums[l] >= base and l > r:
            l -= 1
        while nums[r] <= base and r < l:
            r += 1
        nums[r], nums[l] = nums[l], nums[r]
    nums[low], nums[r] = nums[r], nums[low]
    quicksort(nums, low, r-1)
    quicksort(nums, r+1, high)

快速幂指数求余算法

这个算法可以算是重中之重，蓝桥杯就喜欢搞这些很大数量级的一些问题，而幂指数可以让我们轻松计算这些大数量级指数的问题，很好用，一定要记住。本次省赛和国赛我都用到了这个技巧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def quick_pow(x, n, m):
    if n == 0:
        return 1
    
    if n%2 == 0:
        return quick_pow(x, n // 2, m)  ** 2 % m
    else:
        return quick_pow(x, n-1, m) * x % m
    
    
def quick_pow2(x, n, m):
    if n == 0:
        return 1
    ans = 1
    base = x
    while n > 0:
        if n % 2 == 1:
            ans *= base % m
        base *= base % m
        n //= 2
        
    return ans % m

弗洛伊德最短路算法

图算法也是一个重要考点，需要去理解并记忆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def floyd(W):
    # 首先获取节点数
    node_number = len(W)

    # 初始化路由矩阵
    R = [[0 for i in range(node_number)] for j in range(node_number)]
    for i in range(node_number):
        for j in range(node_number):
            if W[i][j] > 0:
                R[i][j] = j+1
            else:
                R[i][j] = 0
    # 查看初始化的路由矩阵
    for row in R:
        print(row)

    # 循环求W_n和R_n
    for k in range(node_number):
        for i in range(node_number):
            for j in range(node_number):
                if W[i][k] > 0 and W[k][j] > 0 and (W[i][k] + W[k][j] < W[i][j] or W[i][j] == -1):
                    W[i][j] = W[i][k] + W[k][j]
                    R[i][j] = k+1
        print("第%d次循环:" % (k+1))
        print("距离矩阵:")
        for row in W:
            print(row)
        print("路由矩阵:")
        for row in R:
            print(row)

回溯算法

回溯只可意会不可言传，这种回溯的思想才是重中之重，可以帮助你解决很多问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        res = []
        tmp = []
        @cache
        def check(i, j):
            if i >= j:
                return 1
            if s[i] == s[j]:
                return check(i+1, j-1)
            else:
                return 0

        def dfs(i):
            if i == n:
                res.append(tmp[:])
                return
            for j in range(i, n):
                if check(i, j):
                    tmp.append(s[i:j+1])
                    dfs(j+1)
                    tmp.pop()
        
        dfs(0)
        check.cache_clear()
        return res

最后，在leetcode上随便刷刷题，找找写代码的手感，就可以满怀信心的上考场啦！