2024年 蓝桥杯 Python A组题目分析与解说

D.回文数组

D.回文数组

• 起首看这个测试用例的范围，要求我们要使用o(n)的时间复杂度的算法举行求解，相差的题目？那么我们肯定是要看一下对应的位置的这个数字的差值！！！，这是一个很自然的解法，大家要多一点积累
  
• 所以我们要得到一个数组，该数组记载了原始的数组对应的回文位置的数字的差值，这个数组的长度是 n //2,奇数的长度的数组不消考虑中心的那个元素
  
• 接着，题目就转化为将差值数组变为全0数组所需的最少的操纵次数，那么我们起首应该想到这个贪心+罗列的思路
  
• 贪心：尽大概使用对两个元素操纵，迫不得已才可以使用一个元素的操纵，那么什么时候可以使用这个两个元素的操纵？那当然是，当前元素与后面的那一个元素的符号雷同，那么我们就可以同时加或者减去它们的较小值的绝对值
  
• 总体的题目的环境如下：
  
  
  
  • cha*cha[i+1]>0:也就是同号，可以使用两个对象的操纵，操纵完成之后会转化为下面的两个环境的此中一种环境
    
  • cha==0:此时直接continue,不消操纵
    
  • cha*cha[i+1]<0:不同号，只能单独对这个cha自己操纵
    
  
  

2. n = int(input())
3. a = list(map(int,input().split()))
4. cha = [0]*(n//2)
5. # 得到相差的数组
6. for i in range(n//2):
7.   cha[i] = a[i] - a[n-1-i]
8. # 开始贪心枚举
9. ans = 0
10. # 由于要判断后一个的情况，所以最后一个要单独判断
11. for i in range(n//2-1):
12.   if cha[i] == 0:
13.     continue
14.   # 同号的问题
15.   if cha[i]*cha[i+1] > 0:
16.     change = min(abs(cha[i]),abs(cha[i+1]))
17.     ans += change
18.     # 如果是正数
19.     if cha[i] > 0:
20.       cha[i],cha[i+1] = cha[i]-change,cha[i+1]-change
21.            # 如果是负数
22.     else:
23.       cha[i],cha[i+1] = cha[i]+change,cha[i+1]+change
24.   # 如果两个对象的操作没使得当前cha[i]==0,或者是情况3，也就是cha[i]与cha[i+1不同号
25.   if cha[i] == 0:
26.     continue
27.   else:
28.     ans += abs(cha[i])
29. ans += abs(cha[-1])
30. print(ans)

复制代码

F.砍柴

F.砍柴

• 对于这个最优策略的题目：
  
  
  
  • 起首，每次的选择都是选择一个质数，所以你得起首先把最大范围内的质数全部筛选出来，在这里我们使用欧拉筛举行筛选
    
  • 对于最优策略的题目，起首考虑可以使用一个dp数组来记载对应的n所对应的环境下，小蓝可否获胜， 对于当前的n,假如在找到一个dp[n-p]=0,则说明小蓝是可以获胜的，否则就不可
    
  
  

   美中不敷的是，这个代码的时间复杂度过高，只能通过10/20的测试用例，对于最后的dp数组的求解，假如改为10**5+1，则代码会运行很久

1. # 总体来说，就是不断的遍历吧
3. # 首先求解出全部的质数，对于当前的选择，枚举这个<=x的质数，通过这个记忆化很快可以知道
4. dp = [0]*(10**5+1)
5. dp[2],dp[3] = 1,1
6. zhistore = set()
7. iszhi = [True]*(10**5+1)
8. iszhi[0],iszhi[1] = False,False
10. # 使用质数筛，得到 10**5范围内全部的质数
11. for i in range(2,10**5+1):
12.   if iszhi[i]:
13.     zhistore.add(i)
14.   for j in zhistore:
15.     if i * j > 10**5:
16.       break
17.     iszhi[i*j] = False
19. # 全部的质数都存储在这个iszhi中
20. isprime = [i for i,c in enumerate(iszhi) if c == True]
22. for i in range(4,10**4+1):
23.   # 小蓝所做出的选择j
24.   flag = 0
25.   if iszhi[i]:
26.     dp[i] = 1
27.     continue
28.   for j in isprime:
29.     if j>i:
30.       break
31.     if dp[i-j] == 0:
32.       # 表示找到了
33.       flag = 1
34.       dp[i] = 1
35.       break
37. T = int(input())
38. for _ in range(T):
39.   n = int(input())
40.   print(dp[n])

复制代码

• 后面颠末检查，发现照旧这个动态规划存在题目，原本的代码使用的是对于当前的i,查询是否存在减去质数的dp[]是必败的状态，这样的话，服从会十分慢，精确的做法应该是 找到必败的状态dp == 0,然后遍历质数，当前的必败状态i+p的时候对于小蓝来说就是必赢的状态
  

1. # 总体来说，就是不断的遍历吧
3. # 首先求解出全部的质数，对于当前的选择，枚举这个<=x的质数，通过这个记忆化很快可以知道
4. dp = [0]*(10**5+1)
5. dp[2],dp[3] = 1,1
6. zhistore = []
7. iszhi = [True]*(10**5+1)
8. iszhi[0],iszhi[1] = False,False
10. # 使用质数筛，得到 10**5范围内全部的质数
11. for i in range(2,10**5+1):
12.   if iszhi[i]:
13.     zhistore.append(i)
14.   for j in zhistore:
15.     if i * j > 10**5:
16.       break
17.     iszhi[i*j] = False
18.     if i % j == 0:
19.       break
21. # 全部的质数都存储在这个iszhi中
22. isprime = [i for i,c in enumerate(iszhi) if c == True]
24. for i in range(4,10**5+1):
25.   if dp[i] == 0:
26.     for j in isprime:
27.       if i + j < 10**5:
28.         dp[j] = 1
29.         
32. T = int(input())
33. for _ in range(T):
34.   n = int(input())
35.   print(dp[n])

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。