2024年 蓝桥杯 Python A组题目分析与解说
D.回文数组D.回文数组
https://i-blog.csdnimg.cn/direct/787ff7f336584ee3971beec207af45cf.png
https://i-blog.csdnimg.cn/direct/cc538e1df1f646feb57f310e9f73df02.png
[*]起首看这个测试用例的范围，要求我们要使用o(n)的时间复杂度的算法举行求解，相差的题目？那么我们肯定是要看一下对应的位置的这个数字的差值！！！，这是一个很自然的解法，大家要多一点积累
[*]所以我们要得到一个数组，该数组记载了原始的数组对应的回文位置的数字的差值，这个数组的长度是 n //2,奇数的长度的数组不消考虑中心的那个元素
[*]接着，题目就转化为将差值数组变为全0数组所需的最少的操纵次数，那么我们起首应该想到这个贪心+罗列的思路
[*]贪心：尽大概使用对两个元素操纵，迫不得已才可以使用一个元素的操纵，那么什么时候可以使用这个两个元素的操纵？那当然是，当前元素与后面的那一个元素的符号雷同，那么我们就可以同时加或者减去它们的较小值的绝对值
[*]总体的题目的环境如下：
[*]cha*cha>0:也就是同号，可以使用两个对象的操纵，操纵完成之后会转化为下面的两个环境的此中一种环境
[*]cha==0:此时直接continue,不消操纵
[*]cha*cha<0:不同号，只能单独对这个cha自己操纵
n = int(input())
a = list(map(int,input().split()))
cha = *(n//2)
# 得到相差的数组
for i in range(n//2):
cha = a - a
# 开始贪心枚举
ans = 0
# 由于要判断后一个的情况，所以最后一个要单独判断
for i in range(n//2-1):
if cha == 0:
continue
# 同号的问题
if cha*cha > 0:
change = min(abs(cha),abs(cha))
ans += change
# 如果是正数
if cha > 0:
cha,cha = cha-change,cha-change
# 如果是负数
else:
cha,cha = cha+change,cha+change
# 如果两个对象的操作没使得当前cha==0,或者是情况3，也就是cha与cha[i+1不同号
if cha == 0:
continue
else:
ans += abs(cha)
ans += abs(cha[-1])
print(ans)
F.砍柴
F.砍柴
https://i-blog.csdnimg.cn/direct/86004421bfa843e195edd8b0d48a12fe.png
https://i-blog.csdnimg.cn/direct/d3dd85cc80cf4effb782cfeacb3810c3.png
https://i-blog.csdnimg.cn/direct/b04e02ae6b0c433c8e12fc7a7bbd9fcf.png
[*]对于这个最优策略的题目：
[*]起首，每次的选择都是选择一个质数，所以你得起首先把最大范围内的质数全部筛选出来，在这里我们使用欧拉筛举行筛选
[*]对于最优策略的题目，起首考虑可以使用一个dp数组来记载对应的n所对应的环境下，小蓝可否获胜， 对于当前的n,假如在找到一个dp=0,则说明小蓝是可以获胜的，否则就不可
美中不敷的是，这个代码的时间复杂度过高，只能通过10/20的测试用例，对于最后的dp数组的求解，假如改为10**5+1，则代码会运行很久
# 总体来说，就是不断的遍历吧
# 首先求解出全部的质数，对于当前的选择，枚举这个<=x的质数，通过这个记忆化很快可以知道
dp = *(10**5+1)
dp,dp = 1,1
zhistore = set()
iszhi = *(10**5+1)
iszhi,iszhi = False,False
# 使用质数筛，得到 10**5范围内全部的质数
for i in range(2,10**5+1):
if iszhi:
zhistore.add(i)
for j in zhistore:
if i * j > 10**5:
break
iszhi = False
# 全部的质数都存储在这个iszhi中
isprime =
for i in range(4,10**4+1):
# 小蓝所做出的选择j
flag = 0
if iszhi:
dp = 1
continue
for j in isprime:
if j>i:
break
if dp == 0:
# 表示找到了
flag = 1
dp = 1
break
T = int(input())
for _ in range(T):
n = int(input())
print(dp)
[*]后面颠末检查，发现照旧这个动态规划存在题目，原本的代码使用的是对于当前的i,查询是否存在减去质数的dp[]是必败的状态，这样的话，服从会十分慢，精确的做法应该是 找到必败的状态dp == 0,然后遍历质数，当前的必败状态i+p的时候对于小蓝来说就是必赢的状态
# 总体来说，就是不断的遍历吧
# 首先求解出全部的质数，对于当前的选择，枚举这个<=x的质数，通过这个记忆化很快可以知道
dp = *(10**5+1)
dp,dp = 1,1
zhistore = []
iszhi = *(10**5+1)
iszhi,iszhi = False,False
# 使用质数筛，得到 10**5范围内全部的质数
for i in range(2,10**5+1):
if iszhi:
zhistore.append(i)
for j in zhistore:
if i * j > 10**5:
break
iszhi = False
if i % j == 0:
break
# 全部的质数都存储在这个iszhi中
isprime =
for i in range(4,10**5+1):
if dp == 0:
for j in isprime:
if i + j < 10**5:
dp = 1
T = int(input())
for _ in range(T):
n = int(input())
print(dp)
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]