🌻蓝桥杯倒计时18天 小郑通过几道真题把自己的心得总结了一下
🌻再次感谢执梗、杨枝、Pluto.小怂、泡泡几位朋友的帮助
🌻希望对你们有帮助
1.蓝桥杯省赛：一步之遥（填空题）
本题有多种做法，这里利用BFS的方法解释一遍，分享一下我的BFS心得，毕竟蓝桥杯BFS还是很重要的。
单源最短路径型BFS必备的容器，函数:judge()，前驱结点字典pre，队列queue（其实就是列表）,方向数组。下面解释各自的用法：
方向数组：根据题意设置，比如迷宫就需要设置两个方向数组dx和dy，如果是直线型运动的只需要一个方向数组，方向数组用于创建新结点
前驱结点pre：用字典来模拟 pre[i]=j，意思结点i的前驱结点是j（说土一点就是结点i前面那个结点是j）,然后如果有小伙伴对结点这个东西不理解，【没关系，我举个例子，比如在迷宫里面，给你一个坐标（x,y），通过方向数组，借助循环，我们创建了一个新坐标(x1,y1)，如果我们想表示(x1,y1)上一个经过的地方是(x,y)，就可以用pre[(x1,y1)]=(x,y)来表示。在不同场合，结点可以是不同的东西（可以是坐标，一个数...），不必太多纠结（因为这东西本身是从‘’树‘’里面引出来的）】。到此，你可能还不明白创建这样的前驱关系有什么用，没关系，我再举个例子,把pre展开,pre={'(0，0）：（1，1），（1，1）：（2，2），（2，2）：（3，3），（3，3）：（4，5）},根据你所学的知识pre[(4,5)]应该等于（3,3）。然后现在我有五个点，他们的坐标分别是(0，0)（1，1）（2，2）（3，3）（4，5），且已知(0，0）是起点,(4,5)是终点，想请问你，起点到终点的路径长度为多少?下面用一段代码表示,你一定能看懂:通过反复的迭代，使得最终pre[end]=st,每迭代一次，路径+1
st=(0,0) end=(4,5) step=1 while pre[end]!=st: end=pre[end] step+=1 print(step)
所以，pre字典最重要的就是记录前驱关系，当创建完所有结点的关系时，通过终点倒着访问，当访问到起点，结束，总路径因而知晓。
queue:队列,你可以把它简单的理解为一个列表，只不过我们把索引为0的元素取出来，对于队列的作用这里不再赘述，没有基础的建议去看<<算法图解>>（Python语言描述的，对PY党友好)，很快上手
judge:函数，用来判断我们新创建的结点是否合法，合法要根据具体的题意，比如在迷宫里面，坐标不能越界，不能是障碍物，不能已经访问过....
本题而言，属于直线型运动，不妨假设初始点在-97，目标为0，如果搜到0，那么就输出步数。如果没搜到0，把当前结点（数字）的下一个状态也就是新结点加入queue队列（前提要判断过合法），直至找到0。
解释几个细节的地方：judge函数中x in pre.keys()的作用，如果满足条件，说明x已经有了前驱结点，也就是x之前已经被pre[x]这个结点作为新结点创建，也就说明x已经访问过了，从这里也可以看出，每个结点只有一个前驱结点，当所有的结点都创建好了前驱关系，整张图也就搜完了。因此,如果x not in pre.keys(),证明x还没有前驱结点即x还没有被访问过，x合法，tmp(当前结点)可以作为x的前驱结点，否则,x已经有前驱结点，x已经访问过，不合法。如果你还问我为什么已经访问过的为什么不合法，我会告诉你因为第一次访问过的状态已经是距离出发点最近的，那么你已经知道这个状态下结点p距离出发点的距离是最近的，那么下一种状态你又访问到它，它必然不会优于刚刚提到的距离。
AC代码:答案97
dir=[97,-127] def judge(x): if x>0 or x in pre.keys(): return False else: return True pre={} queue=[-1] def bfs(): global queue while queue: tmp=queue.pop(0) if tmp==0: step=1 while pre[tmp]!=-1: tmp=pre[tmp] step+=1 print(step) break else: for i in range(2): ne=tmp+dir[i] if judge(ne): queue.append(ne) pre[ne]=tmp bfs()
2.ACWing蓝桥杯模拟赛:农田灌溉
这是一个多源BFS的问题，求最短距离。
与单源不同的地方在于，它需要单独创建一个列表d,d[i]代表第i个农田被灌满的最短时间
还多了一个递推关系：如果i的前驱结点是j，d[i]=d[j]+#单独灌满第i个农田花费的时间
一开始的出发点，也就是初始的几个多源，入队，把他们走一次能够访问到的结点p入队，（前提p合法），并更新d[p]。这里判断p的合法性：如果d[p]不等于初始化的值，说明未访问过，合法，否则已经记录灌满p的最短时间，无需入队，不合法。
所以唯一不同点在于，多了一个记录列表，不同的合法性判断条件，其他都一样。
AC代码
t=int(input()) def bfs(n,k,a): d=[-float('inf') for i in range(n+1)]#第i个农田被覆盖的最短时间 for i in a: d[i]=1 queue=a.copy() dir=[-1,1] while queue: tmp=queue.pop(0) for i in range(2): ne=tmp+dir[i] if 1<=ne<=n and d[ne]==-float('inf'): d[ne]=d[tmp]+1 queue.append(ne) print(max(d)) for i in range(t): n,k=map(int,input().split()) a=list(map(int,input().split())) bfs(n,k,a)
3.NOIP提高组：跳石头 洛谷P2678
这道题和蓝桥杯算法提高：打包很像！
观察他们的问题：最短跳跃距离最大，最小的最大重量；
这一类题目往往可以通过二分答案来找到解，二分答案需要两个条件：有界性和单调性
有界性显然，因为整段路是L，所以答案一定小于等于L，单调性是因为如果我取了一个mid不符合，那么比mid更大的一定不符合，因为要搬的石头会更多了，如果mid符合，比mid小的一定符合，因为不需要搬的石头更多了，那我只需要往mid的右边找，直至找到最优解。
你可能有疑惑的地方:比mid更大的一定不符合，因为要搬的石头会更多了 这句话是为什么，我解释一下，比方说你mid=5，那么你就去check 5是不是可行解，怎么判断是不是可行解：首先，mid=5意味着你假设了最短距离5，设想你站在一个石头上，那么如果两个石头间距超过5，下一个石头就不需要搬走，因为最短距离是5，所以你直接跳过去，到达下一个石头。
现在，距离下一个石头的长度1，表明两石头的间距是1，这与你的假设矛盾，所以它必须搬走，计数器累加1，现在距离你为1的这个石头已经搬走了。现在你的前面又面临着一个石头，如果它距离你所处的石头的长度小于5，那么它就必须搬走，否则，你就可以直接跳过去。那么一直跳到终点，计数器统计的步数s和m(题目运行的搬走个数)比较，如果s>m,显然不符合，回到开始的问题，如果mid'>mid，那么s">=s>m,要搬的石头显然要增加，就更不符合了。同理，如果mid是一个可行解,mid'<mid，那么需要搬的石头显然更少，就一定符合。
AC代码
L,N,M=map(int,input().split()) a=[int(input()) for i in range(N)] a.insert(len(a),L) if N==0: print(L) elif M==0: print(min(a)) else: l,r=-1,100000001 def check(x): cnt=0 flg=0 for i in range(N): if a[i]-flg<x: cnt+=1 else: flg=a[i] return cnt<=M while l+1!=r: mid=(l+r)//2 if check(mid): l=mid else: r=mid print(l)
希望uu们都能在蓝桥杯取得理想成绩！冲击省一
