Python|【蓝桥杯真题】Python备战28天蓝桥杯|leetcode|算法|散列表|笔

距离蓝桥杯28天即使是周末也要按时完成打卡
文章图片
下面对执梗大哥提供的每日真题训练提供题解
''所有题目均在蓝桥杯官网或者蓝桥云课找到''

1.猴子分香蕉

文章图片

问题分析：假设一开始有x个第一只猴子做完事情后剩下[(x-1)/5]*4个香蕉记作x1
第二只猴子做完事情后剩下[(x1-2)/5]*4个香蕉记作x2
第三只猴子做完事情后剩下[(x2-3)/5]*4个香蕉记作x3...
由此xn+1=[(xn-j)/5]*4 我们只需要保证最后一次的香蕉是5的倍数大功告成！
细节的地方：每次循环的时候要保证(x-j)大于0且是5的倍数
【Python|【蓝桥杯真题】Python备战28天】就是一道很简单的找规律的题目
文章图片
代码已经AC

for i in range(4,10000): x=i for j in range(1,5): if (x-j)%5!=0 or x-j<=0:#保证整除5且平分之前个数大于0 break x=int((x-j)/5)*4 else: if x%5==0: print(i) break#3141

2.等差数列

文章图片

问题分析：根据等差数列的通项公式要使得项数最小必然公差最大
公差不能无限大要有制约，约束的条件是从出发点开始保证能通过N次的公差累加达到后续的每一个数字
假设有5个数字前后两两相差 a,b,c,d 为保证从第一个数字st开始经过nd能遍历(st+a,st+a+b,st+a+b+c,st+a+b+c+d) ，如果公差取的太大，会导致无法到达其中某一个数（不连续了），如果公差取的太小，即便能遍历，长度也不符合题意。
那该如何抉择这个问题呢？由前面提到，要使得公差最大，我们可以联想到gcd（最大公约数），但是现在有4个数（上面提到的a,b,c,d），与以往gcd（a,b）有所不同，大胆去尝试，如果gcd（a,b,c,d) ，代表着什么？代表着两两作差的数所组成的集合，在这个集合里面所有数的最大公约数。假设gcd(a,b,c,d)=p ，那么其中任意一个数字，一定能够用kp表达同时,这就意味着，一定能够刚从出发点经过n次的累加达到其他任意一个点。又因为是最大公约数而不仅仅是公约数，在这个强条件下，经过的步数一定是最短的，即项数最少。
代码已AC
文章图片

n=int(input())l=list(map(int,input().split()))l.sort()#项数=[(an-a1)/d]+1 d最大易想到最大公约数 #观察数据发现应该需要求出n个数之间的最大公约数 def gcd(a,b): while b: a,b=b,a%b return adef l_gcd(nums): if len(nums)==1: return nums[0] elif len(nums)==2: return gcd(nums[0],nums[1]) else: return gcd(l_gcd(nums[:len(nums)//2]),l_gcd(nums[len(nums)//2:]))if max(l)==min(l): print(n) else: t=[l[i]-l[i-1] for i in range(1,n)] d=l_gcd(t) print(int((l[-1]-l[0])/d+1))

3.平方序列

文章图片

for x in range(2020,100000): for y in range(x,100000): if 2*x**2==2019**2+y**2: print(x+y)

问题分析：
文章图片
暴力就好了，注意细节的地方y>x，蓝桥杯的简单题目做到不丢分，细致。

4.倍数问题

文章图片

问题分析：已经第九题了可以先试试暴力骗分有30分

#暴力法 30分 n,k=map(int,input().split()) ans=0l=list(map(int,input().split()))import itertoolsfor i in itertools.combinations(l,3): p=list(i) if sum(p)>ans and sum(p)%k==0: ans=sum(p) print(ans)

当然还是要正紧做 AC才是我们的最终目标
文章图片

不过目前小郑还没有做出来想了挺久的附上AC的PY思路吧
来源一位DL：

n, k = map(int,input().split()) r = [[0] * 3 for i in range(k)] #记录余数，每个余数记录最大的三个数a、b、ca = input().split() # 输入数据就分组同余一组维持每组最大的三个数用插入排序 for i in range(len(a)): re = int(a[i]) % k if int(a[i]) > r[re][0]: r[re][2], r[re][1], r[re][0] = r[re][1], r[re][0], eval(a[i]) elif int(a[i]) > r[re][1]: r[re][2], r[re][1] = r[re][1], eval(a[i]) elif int(a[i]) > r[re][2]: r[re][2] = eval(a[i]) Max = 0 # 按照余数枚举 for i in range(k): for j in range(i, k): tmp = (k - i + k - j) % k v1 = r[i][0]#a的余数 if i == j: v2 = r[i][1]#如果b的余数和a的余数相同 if i == tmp:#如果c的余数和a也相同 v3 = r[i][2] else: v3 = r[tmp][0] else:#如果b的余数和a的余数不同 v2 = r[j][0] if i == tmp:v3 = r[i][1] elif j == tmp: v3 = r[j][1] else:v3 = r[tmp][0] if v1 + v2 + v3 > Max: Max = v1 + v2 + v3 print(Max)