【蓝桥杯真题】提升篇 详解 Python_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])

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