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

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

1.蓝桥杯省赛:一步之遥(填空题)

image.png


本题有多种做法,这里利用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蓝桥杯模拟赛:农田灌溉



image.png



这是一个多源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

image.png



这道题和蓝桥杯算法提高:打包很像!


观察他们的问题:最短跳跃距离最大,最小的最大重量;


这一类题目往往可以通过二分答案来找到解,二分答案需要两个条件:有界性和单调性


有界性显然,因为整段路是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)
目录
相关文章
|
2月前
|
Python
蓝桥杯练习题(一):Python组之入门训练题
这篇文章是关于蓝桥杯Python组的入门训练题,包括Fibonacci数列、圆的面积、序列求和和A+B问题的具体代码实现和样例输出。
136 0
|
2月前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
88 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
2月前
|
人工智能 Python
蓝桥杯练习题(四):Python组之历届试题三十题
关于蓝桥杯Python组历届试题的三十个练习题的总结,包括题目描述、输入输出格式、样例输入输出以及部分题目的解题思路和代码实现。
39 0
蓝桥杯练习题(四):Python组之历届试题三十题
|
2月前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(二):Python组之基础练习三十题
蓝桥杯Python编程练习题的集合,包含了三十个不同难度的编程题目,覆盖了基础语法、数据结构和算法等领域。
42 0
|
7月前
|
索引 Python 容器
【备战蓝桥杯】探索Python内置标准库collections的使用
【备战蓝桥杯】探索Python内置标准库collections的使用
97 1
|
7月前
|
开发者 Python
【备战蓝桥杯】如何使用Python 内置模块datetime去计算我与CSDN相遇的天数
【备战蓝桥杯】如何使用Python 内置模块datetime去计算我与CSDN相遇的天数
72 1
|
7月前
|
算法 测试技术 编译器
蓝桥杯-02-python组考点与14届真题
蓝桥杯-02-python组考点与14届真题
|
Python
对Python中一些“坑”的总结及技巧
一.赋值即定义 1.运行以下代码会出现报错 #!/usr/bin/env python #_*_conding:utf-8_*_ x = 100 def outer(): def inner(): x += 100    #其实这里等效于"x = x + 100",我们直到这是一个赋值语句,会优先计算右边的等式,即"x + 100".而在此时由于x变量赋值即定义,即此时的x和全局作用域的x并非同一个对象。
762 0
|
8天前
|
人工智能 数据可视化 数据挖掘
探索Python编程:从基础到高级
在这篇文章中,我们将一起深入探索Python编程的世界。无论你是初学者还是有经验的程序员,都可以从中获得新的知识和技能。我们将从Python的基础语法开始,然后逐步过渡到更复杂的主题,如面向对象编程、异常处理和模块使用。最后,我们将通过一些实际的代码示例,来展示如何应用这些知识解决实际问题。让我们一起开启Python编程的旅程吧!
|
7天前
|
存储 数据采集 人工智能
Python编程入门:从零基础到实战应用
本文是一篇面向初学者的Python编程教程,旨在帮助读者从零开始学习Python编程语言。文章首先介绍了Python的基本概念和特点,然后通过一个简单的例子展示了如何编写Python代码。接下来,文章详细介绍了Python的数据类型、变量、运算符、控制结构、函数等基本语法知识。最后,文章通过一个实战项目——制作一个简单的计算器程序,帮助读者巩固所学知识并提高编程技能。