距离蓝桥杯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])
有任何疑惑欢迎提问！程序题还是要自己多尝试多实践！
