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)