锐客网

  1. 首页 > it技术 > >

Python|【蓝桥杯真题】提升篇 详解 Python

算法Python笔记蓝桥杯

Python|【蓝桥杯真题】提升篇 详解 Python
文章图片
距离蓝桥杯25天
Python|【蓝桥杯真题】提升篇 详解 Python
文章图片
欢迎来到Python蓝桥杯提升篇
Python|【蓝桥杯真题】提升篇 详解 Python
文章图片
难度依次提升 做好心理准备噢
1.巧排扑克牌Python|【蓝桥杯真题】提升篇 详解 Python
文章图片
Python|【蓝桥杯真题】提升篇 详解 Python
文章图片

问题分析：手算 作图模拟 编号0-12 ，0作为"最底层的牌"" ,即下面规定越靠近左侧越下面
第一轮 可以确定6个数字，因为都是隔着一项出牌，在对应编号上写上对应数字
由于12以后看似没有牌了，我们需要重新组合，在第一轮过程中，未被编号的将后移，注意顺序
Python|【蓝桥杯真题】提升篇 详解 Python
文章图片

结果：
print('7, A, Q, 2, 8, 3, J, 4, 9, 5, K, 6, 10')

2.质数拆分 Python|【蓝桥杯真题】提升篇 详解 Python
文章图片
Python|【蓝桥杯真题】提升篇 详解 Python
文章图片

问题分析：先用埃筛法 把0—2019的质数选出来 存入数组Prime
然后利用背包的思想对于第j个质数，只有取和不取的两种可能
dp[i][j]:代表从j个质数中选 恰好和为i的方案数
那么dp[i][j]=prime[j]不取的方案数+prime[j]取的方案数，i为背包容量（总数和）
如果prime[j]>i,那么prime[j]取的方案数=0
如果prime[j] 最后初始化dp[0]全部设为1
结果：55965365465060
max=2019is_prime=[1]*2020#is_prime[i]代表i是否为素数，是为1，不是为0prime=[0]#埃筛 特殊将0作为第0个质数for i in range(2,max+1): if is_prime[i]: prime.append(i) j=i+i while j<=max: is_prime[j]=0 j+=i#dp[i][j]代表从j个质数中选 恰好和为i的方案数 #dp[i][j]=prime[j]不取的方案数+prime[j]取的方案数 #若prime[j]<=i:dp[i][j]=dp[i-prime[j]][j-1]+dp[i][j-1] #如果prime[j]>i dp[i][j]=dp[i][j-1] n=len(prime) dp=[[0]*(n) for i in range(0,2020)] dp[0]=[1]*(n)for i in range(1,2020): for j in range(1,n): if prime[j]>i: dp[i][j]=dp[i][j-1] else: dp[i][j]=dp[i-prime[j]][j-1]+dp[i][j-1]print(dp[2019][-1])

3.日志统计Python|【蓝桥杯真题】提升篇 详解 Python
文章图片
Python|【蓝桥杯真题】提升篇 详解 Python
文章图片

问题分析：签到题，需要用到‘’字典‘’，以Id为Key，r[id]=[t1,t2,t3...]，将点赞时刻填入列表。
将列表升序排列，遍历列表，以点赞数目K为间距，如果时间差<=d，符合，id可选。
代码已经AC
n,d,k=map(int,input().split())r=dict() for i in range(n): ts,id=map(int,input().split()) if id not in r.keys(): r[id]=[ts] else: r[id].append(ts)s=[]#记录符合的idfor i in r.keys(): l=r[i] l.sort() if len(l)

4. 递增三元组Python|【蓝桥杯真题】提升篇 详解 Python
文章图片
Python|【蓝桥杯真题】提升篇 详解 Python
文章图片

问题分析：遍历数组b，当访问到b[i]，统计a中b[i]的个数q
cnt：作为答案输出; 统计完后,cnt+=p*q
那么该如何统计？
最简单的方法:先将a,c排序 遍历a(c)，统计个数即可 但这样只能过75分
n=int(input()) a=list(map(int,input().split())) b=list(map(int,input().split())) c=list(map(int,input().split()))a.sort() c.sort(reverse=True)cnt=0for i in range(n): j,k=0,0 t=b[i] while j<=n-1 and a[j]t:k+=1 cnt+=j*k print(j,k) print(cnt)#超时 75分

如何优化：利用前缀和，用空间换时间，每次统计的时候直接从列表查询
对于数组a而言，创建一个列表ans,ans[i]代表i在数组a中出现的次数
对于数组c而言，创建一个列表cns,cns[i]代表i在数组c中出现的次数
创建一个数组x,作为ans的前缀和,x[i]代表数组a中<=i的数字出现的次数
创建一个数组y,作为cns的前缀和,y[i]代表数组c中<=i的数字出现的次数
对于一个一个确定的b[i] 我们统计a中 【Python|【蓝桥杯真题】提升篇 详解 Python】对于一个一个确定的b[i] 我们统计c中>b[i]的个数，即查询q=y[-1]-y[b[i]]
细节的地方：对于x[b[i]-1]，b[i]-1有可能越界，即b[i]-1>len(x)-1
那么q=x[-1],这是由于a中最大的元素可能比b[i]-1还要小，所以此时前缀和x的最大下标小于b[i]-1，那么a中小于b[i]的个数一定也就是x[-1]个
同时，b[i]-1有可能变为负数，，即b[i]<1，即b[i]=0，但那对应的x[b[i]-1]并不是我们想要的。实际上，这种特殊情况,p=0，因为a中不会有比0更小的数字了。
对于y[-1]-y[b[i]],y[b[i]]有可能越界，如果len(y)-1<=b[i]，那么意味着c中最大的元素小于b[i]，那么q=0，因为c中不会有比b[i]更大的数字了。
Python|【蓝桥杯真题】提升篇 详解 Python
文章图片

n=int(input()) a=list(map(int,input().split())) b=list(map(int,input().split())) c=list(map(int,input().split()))ans=[0 for i in range(max(a)+1)] for i in a: ans[i]+=1x=[0 for i in range(max(a)+1)] x[0]=a.count(0) for j in range(1,max(a)+1): x[j]=x[j-1]+ans[j]cns=[0 for i in range(max(c)+1)] for i in c: cns[i]+=1y=[0 for i in range(max(c)+1)] y[0]=c.count(0) for j in range(1,max(c)+1): y[j]=y[j-1]+cns[j]cnt=0 for k in range(n): if b[k]-1>len(x)-1: p=x[-1] elif b[k]-1<0: p=0 else: p=x[b[k]-1] if len(y)-1<=b[k]: q=0 else: q=y[-1]-y[b[k]] cnt+=p*q print(cnt)

5. 发现环Python|【蓝桥杯真题】提升篇 详解 Python
文章图片
Python|【蓝桥杯真题】提升篇 详解 Python
文章图片

问题分析：利用拓扑排序来检测环 可以看我之前这篇文章
!!如果对拓扑排序没有理解的，下面讲的会很难理解，需要基于对拓扑排序的理解基础！
与有向图应用的拓扑排序不同：我们需要做几点改变
第一个就是入度的概念：之前的入度指的是其他点指向u点的边数
这里由于是无向图 只要其他点连着u点，不论方向，边数都应该累加进来
第二个就是：原有删除结点是基于该结点的入度为0，这里需要稍作改变，改作入度为1
其他的保持不变，最后输出[1,2....,N]和拓扑序列seq的差集再排序一下就好了
Python|【蓝桥杯真题】提升篇 详解 Python
文章图片

#构图 n=int(input())G=dict((i,[]) for i in range(1,n+1)) for i in range(n): x,y=map(int,input().split()) G[x].append(y) G[y].append(x) indegrees=dict((i,0) for i in G.keys())for i in G.keys(): for j in G[i]: indegrees[j]+=1 stack=[i for i in indegrees.keys() if indegrees[i]==1] seq=[]#拓扑序列while stack: tmp=stack.pop() seq.append(tmp) for i in G[tmp]: indegrees[i]-=1 if indegrees[i]==1: stack.append(i) ans=list(set([i for i in range(1,n+1)])-set(seq)) ans.sort() for i in range(len(ans)-1): print(ans[i],end=' ') print(ans[-1])

有任何疑惑欢迎提问！程序题还是要自己多尝试多实践！

    推荐阅读


    上一篇：蓝桥杯|蓝桥杯python（扫地机器人）

    下一篇：java实现第三届蓝桥杯机器人行走