一、本周周赛总结

• 跑路。
• T1 贪心模拟。
• T2 原题。
• T3 贪心。
• T4 树上倍增。
  

2833. 距离原点最远的点

2833. 距离原点最远的点

1. 题目描述

2. 思路分析

• 由于l和r是固定要移动的，那么先把l和r移动完，然后把下划线按照当前方向继续移动就好了。

3. 代码实现

class Solution:def furthestDistanceFromOrigin(self, moves: str) -> int:cnt1 = moves.count('L')cnt2 = moves.count('R')return abs(cnt1 - cnt2) + moves.count('_')

2834. 找出美丽数组的最小和

2834. 找出美丽数组的最小和

2. 思路分析

• 和上周k-avoiding数组是同一道题。

3. 代码实现

class Solution:def minimumPossibleSum(self, n: int, target: int) -> int:vis = set()pos = 1s = 0while len(vis) < n:if target - pos not in vis:s += posvis.add(pos)pos += 1return s

2835. 使子序列的和等于目标的最少操作次数

2835. 使子序列的和等于目标的最少操作次数

1. 题目描述

2. 思路分析

有个结论，对于x=2^k,那么nums中所有<=x的数加起来>=x，则一定能组合出x，否则不能。

• 按照这个结论，从低位到高位模拟，如果不能组合，则去拆一个更大的数，拆到当前位即可。

3. 代码实现

class Solution:def minOperations(self, nums: List[int], target: int) -> int:if sum(nums)<target:return -1cnt = [0]*32ts = [0]*32for v in nums:cnt[v.bit_length()-1] += 1for i in range(32):if target>>i&1:ts[i] = 1 s = 0ans = 0 for i in range(32):s += cnt[i]<<i if ts[i]:if s >= (1<<i):s -= 1<<i else:j = i+1while not cnt[j]:j += 1while j !=i:cnt[j]-=1j-=1cnt[j]+=2ans += 1return ans

2836. 在传球游戏中最大化函数值

[2836. 在传球游戏中最大化函数值]https://leetcode.cn/problems/maximize-value-of-function-in-a-ball-passing-game/)

1. 题目描述

2. 思路分析

这题存在O(n)做法，要建立基环树森林，然后从环逆向处理，代码量大，不好写。

• 由于看到k很大，且能转移，考虑倍增:预处理出从每个位置走k步能得到的分数，然后枚举每个位置即可。
• 注意分数要加上两端的编号，因此定义f[i][j]为从i位置出发，走2^j步，排除i经过的编号和。
• 那么f[i][j+1]=f[i][j]+f[p][j],其中p是i走2^j步的位置。

3. 代码实现

class Solution:def getMaxFunctionValue(self, receiver: List[int], k: int) -> int:n = len(receiver)m = k.bit_length()f = [receiver] + [[0]*n for _ in range(m+1)]pa = [receiver] + [[0]*n for _ in range(m+1)]for i in range(m-1):for j in range(n):p = pa[i][j]pa[i+1][j] = pa[i][p]f[i+1][j] = f[i][p] + f[i][j]ans = 0for i,v in enumerate(receiver):s = ifor j in range(k.bit_length()):if k >> j&1:s += f[j][i]i = pa[j][i]ans = max(ans,s)return ans      

参考链接