代码收藏家 【蓝桥杯真题】提升篇 详解 Python
距离蓝桥杯25天
欢迎来到Python蓝桥杯提升篇
难度依次提升 做好心理准备噢
1.巧排扑克牌
问题分析：手算 作图模拟 编号0-12 ，0作为"最底层的牌"" ,即下面规定越靠近左侧越下面
第一轮 可以确定6个数字，因为都是隔着一项出牌，在对应编号上写上对应数字
由于12以后看似没有牌了，我们需要重新组合，在第一轮过程中，未被编号的将后移，注意顺序
结果：
print('7, A, Q, 2, 8, 3, J, 4, 9, 5, K, 6, 10')
2.质数拆分 
问题分析：先用埃筛法 把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]<i ,那么prime[j]可取，prime[j]取的方案数！=0，因而其的计算方法为：在i的容量大小下预留prime[j]的空间 前j-1个质数可构成的方案
最后初始化dp[0]全部设为1
结果：55965365465060
max=2019
is_prime=[1]*2020#is_prime[i]代表i是否为素数，是为1，不是为0
prime=[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.日志统计
问题分析：签到题，需要用到‘’字典‘’，以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=[]#记录符合的id
for i in r.keys():
l=r[i]
l.sort()
if len(l)<k:
continue
for j in range(len(l)):
if j+k-1<=len(l)-1:
if l[j+k-1]-l[j]<=d-1:
s.append(i)
break
s.sort()
for i in s:
print(i)
4. 递增三元组
问题分析：遍历数组b，当访问到b[i]，统计a中<b[i]的个数p，统计c中>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=0 for i in range(n): j,k=0,0 t=b[i] while j<=n-1 and a[j]<t:j+=1 while k<=n-1 and c[k]>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中<b[i]的个数，即查询p=x[b[i]-1]
对于一个一个确定的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]更大的数字了。
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]+=1
x=[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]+=1
y=[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. 发现环
!!如果对拓扑排序没有理解的，下面讲的会很难理解，需要基于对拓扑排序的理解基础！
与有向图应用的拓扑排序不同：我们需要做几点改变
第一个就是入度的概念：之前的入度指的是其他点指向u点的边数
这里由于是无向图 只要其他点连着u点，不论方向，边数都应该累加进来
第二个就是：原有删除结点是基于该结点的入度为0，这里需要稍作改变，改作入度为1
其他的保持不变，最后输出[1,2….,N]和拓扑序列seq的差集再排序一下就好了
#构图
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])
有任何疑惑欢迎提问！程序题还是要自己多尝试多实践！
来源：Py小郑
