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)