当前位置:   article > 正文

第十四届 蓝桥杯省赛 PythonB组 个人解题思路_蓝桥杯python第十四届b组

蓝桥杯python第十四届b组

  1. s = input().strip()
  2. dp = [0] * (len(s) + 1)
  3. dp[1] = ord(s[0]) - 96
  4. for i in range(2,len(s) + 1):
  5. dp[i] = max(dp[i - 2] + ord(s[i - 1]) - 96,dp[i - 1])
  6. print(dp[len(s)])

  1. #第I题:样例输入第一行为"4 4"
  2. #二分答案 + 区间合并
  3. def check(t):#判断t时刻 是否能让管道全部检测到水
  4. brr = []#每个在t时刻 打开的阀门的左右区间 宽度
  5. for i in range(n):
  6. if arr[i][0] > t:break
  7. Si,Li = arr[i]
  8. #保持l最小是1 r最大是Len 超过就没有必要判断了
  9. l,r = max(1,Li - (t - Si)),min(Len,Li + (t - Si))
  10. brr.append((l,r))
  11. brr.sort(key=lambda x:x[0])#按左端点排序
  12. #区间合并
  13. end = 0
  14. for l,r in brr:
  15. if l - end > 1:return False
  16. end = max(end,r)
  17. if end == Len:return True
  18. return end == Len
  19. def main():
  20. l,r = 1,Len + arr[-1][0] + 100
  21. ans = r
  22. while l <= r:
  23. mid = (l + r) // 2
  24. if check(mid):ans = mid;r = mid - 1
  25. else:l = mid + 1
  26. return ans
  27. n,Len = map(int,input().strip().split())
  28. arr = list()#阀门a[i][0]-什么时刻打开 a[i][1] - 阀门编号
  29. for i in range(n):
  30. L,S = map(int,input().strip().split())
  31. arr.append((S,L))
  32. arr.sort(key=lambda x:x[0])#按打开时刻排序
  33. ans = main()
  34. print(ans)

 

  1. #贪心 低位 -> 高位 遍历
  2. #每次衡量当前位 到目标值 所需最小花费
  3. #进位后,还要判断对进位后数字的影响
  4. #返回x[u] 一直加1 到与y[u]位相同所需要的花费和加完后有改动的字符串
  5. def count(u,t):
  6. res = 0
  7. while u != 0 and t != 0:
  8. c = x[u]
  9. sub = (c - y[u] + 10) % 10
  10. jf = (y[u] - c + 10) % 10
  11. after = min(sub,jf)#进位前需要的最小花费
  12. c += t
  13. if c == 10:c = 0;t = 1
  14. elif c == -1:c = 0;t = -1
  15. else:t = 0
  16. sub = (c - y[u] + 10) % 10
  17. jf = (y[u] - c + 10) % 10
  18. now = min(sub,jf)#进位后需要的最小花费
  19. res += now - after
  20. u -= 1
  21. return res
  22. #加法
  23. def Sum(u):
  24. res = y[u] - x[u]
  25. if res < 0:
  26. #否则表示要进位
  27. res = y[u] + 10 - x[u]
  28. res += count(u - 1,1)
  29. return res
  30. #减法
  31. def Mul(u):
  32. res = x[u] - y[u]
  33. if res < 0:
  34. #否则表示要借位
  35. res = x[u] + 10 - y[u]
  36. res += count(u - 1,-1)
  37. return res
  38. def main():
  39. ans = 0#要移动的次数
  40. r = n - 1
  41. while r >= 0:
  42. if x[r] == y[r]:r -= 1;continue
  43. SumCnt,MulCnt = Sum(r),Mul(r)
  44. ## print(SumCnt,MulCnt)
  45. if SumCnt <= MulCnt:#做加法
  46. ans += (y[r] - x[r] + 10) % 10
  47. ## print("Sum",r,ans,(y[r] - x[r] + 10) % 10)
  48. if y[r] < x[r]:#说明进位了
  49. t,i = 1,r - 1#向前进位
  50. while i != -1 and t != 0:
  51. if x[i] == 9:x[i] = 0;t = 1
  52. else:x[i] += t;t = 0
  53. i -= 1
  54. else:#做减法
  55. ans += (x[r] - y[r] + 10) % 10
  56. ## print("Mul",r,ans,(x[r] - y[r] + 10) % 10)
  57. if y[r] > x[r]:#要借位
  58. t,i = -1,r - 1
  59. while i != -1 and t != 0:
  60. if x[i] == 0:x[i] = 9;t = -1
  61. else:x[i] += t;t = 0
  62. i -= 1
  63. ## print(x[:r])
  64. r -= 1
  65. return ans
  66. n = int(input().strip())
  67. x,y = list(map(int,input().strip())),list(map(int,input().strip()))
  68. ##print(n,x,y)
  69. ans = main()
  70. print(ans)

我题意理解错了,我理解成选了第i层后,第i-1和第i+1层都不能选...

  1. def add(a,b):
  2. node.append((b,h[a]))
  3. h[a] = len(node) - 1
  4. def dfs(f,root):
  5. #要么选
  6. floot[f].append(root)
  7. t = h[root]
  8. while t != -1:
  9. b,t = node[t]
  10. dfs(f + 1,b)
  11. def main():
  12. for i in range(n,0,-1):
  13. for j in floot[i]:
  14. dp[i] = max(dp[i],v[j])
  15. if i + 2 <= n:dp[i] += dp[i + 2]
  16. n = int(input().strip())
  17. node,h = [0],[-1] * (n + 1)#邻接表存储树
  18. par = list(map(int,input().strip().split()))
  19. v = list(map(int,('0 ' + input()).strip().split()))
  20. for i in range(2,n + 1):
  21. add(par[i - 2],i)
  22. floot = [[] for i in range(n + 1)]#每一层的结点有哪些
  23. dfs(1,1)#划分层级
  24. dp = [0] * (n + 1)
  25. main()
  26. ans = dp[1]
  27. if n >= 2:ans = max(ans,dp[2])
  28. print(ans)

 

  1. def add(x,y,z):
  2. node.append((y,z,h[x]))
  3. h[x] = len(node) - 1
  4. def dijk(start):
  5. dis[start] = 0
  6. for i in range(n):
  7. t = -1
  8. for j in range(n):
  9. if st[j]:continue
  10. if t == -1 or dis[t] > dis[j]:
  11. t = j
  12. st[t] = True
  13. j = h[t]
  14. while j != -1:
  15. y,z,j = node[j]
  16. if st[y]:continue
  17. if dis[y] == dis[t] + z:
  18. path[y].append(t)
  19. elif dis[y] > dis[t] + z:
  20. dis[y] = dis[t] + z
  21. path[y] = [t]#只能从t转移
  22. def count(x):
  23. res,st = 0,[False] * (n + 1)
  24. Que = [x]
  25. while len(Que) != 0:
  26. t = Que.pop()
  27. if st[t]:continue
  28. for i in path[t]:
  29. if i == 1:
  30. res += 1
  31. st[t] = True
  32. else:
  33. Que.append(i)
  34. return res
  35. n,m = map(int,input().strip().split())
  36. node,h = [0],[-1] * (n + 1)
  37. for i in range(m):
  38. x,y,z = map(int,input().strip().split())
  39. add(x,y,z)
  40. add(y,x,z)
  41. dis,st = [float('inf')] * (n + 1),[False] * (n + 1)
  42. path = [[] for i in range(n + 1)]#i从哪个最短路过来的
  43. dijk(1)
  44. path[1] = [1]#1默认是从自己过来的
  45. for i in range(1,n + 1):
  46. if dis[i] == float('inf'):print(-1)
  47. else:print(count(i) - 1)

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/很楠不爱3/article/detail/447255
推荐阅读
相关标签
  

闽ICP备14008679号