【蓝桥杯真题】18天Python组冲刺 心得总结

🌻蓝桥杯倒计时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们都能在蓝桥杯取得理想成绩!冲击省一

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>