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

本人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上随便刷刷题,找找写代码的手感,就可以满怀信心的上考场啦!