第 369 场周赛（3题，递归式动态规划）

第一题

在这里插入图片描述
简单题，就不多写了

class Solution:
    def findKOr(self, nums: List[int], k: int) -> int:
        ans = [0] * 31
        for n in nums:
            for i in range(31):
                if 2**i & n == 2**i:
                    ans[i] += 1
        
        return sum([2**i if ans[i] >= k else 0 for i in range(31)])

第二题

在这里插入图片描述

0 至少被替换为 1，所以替换完成后两个数组的所有元素的和的最小值 = 替换前元素的和 + 数组中 0 的数量
只有当一个数组中没有0（即它的元素和无法增大），且它的元素和小于另一个数组替换后的所有元素和的最小值的时候，才会返回 -1
当两个数组中都有 0 时，那么答案就是 max(替换完成后两个数组的所有元素的和的最小值)

class Solution:
    def minSum(self, nums1: List[int], nums2: List[int]) -> int:
        n10, n20, sum1, sum2 = 0, 0, 0, 0
        for n in nums1:
            if n == 0:
                n10 += 1
            sum1 += n
        for n in nums2:
            if n == 0:
                n20 += 1
            sum2 += n
        if n10 == 0 and sum2 + n20 > sum1:
            return -1
        if n20 == 0 and sum1 + n10 > sum2:
            return -1
        return max(sum1 + n10, sum2 + n20)

第三题

在这里插入图片描述
赛中思路：

题目理解为，在数组中任意连续的三个数中，必有一个元素大于等于 k
对于任意一个数我们可以选择将它变成大于等于 k 的数，或者不对它进行操作
定义动态规划数组 t[i][j]，其中 t[i][0] 表示在把 nums[i] 变成大于等于 k 的前提下 nums[ :i + 1] 为美丽数组的最小递增运算数，t[i][1] 表示在不对 nums[i] 操作的前提下 nums[ :i + 1] 为美丽数组的最小递增运算数
更新 t[i][0] ，因为要把 nums[i] 更新为大于等于 k 的数，那么 i - 1， i - 2， i - 3必有一个是 k ，但我们不知道是哪一个，所以取 min(t[i - 3][0], t[i - 2][0], t[i - 1][0])
更新 t[i][1] ，此时不操作 nums[i]，那么为了使得 i，i - 1，i - 2，中有一个为 k，所以取 min(t[i - 2][0], t[i - 1][0])
通过4，5两步发现在更新值时不需要 t[i][1] 的数据，所以就不用第 5 步了

class Solution:
    def minIncrementOperations(self, nums: List[int], k: int) -> int:
        t = [0] * len(nums)
        t[0] = max(k - nums[0], 0)
        t[1] = max(k - nums[1], 0)
        t[2] = max(k - nums[2], 0)
        for i in range(3, len(nums)):
            t[i] = min(t[i - 3], t[i - 2], t[i - 1]) + max(k - nums[i], 0)
        return min(t[-1], t[-2], t[-3])

第四题

在这里插入图片描述
困难，还是一如既往的不会做，下面贴一下大佬小羊肖恩的题解

我们定义状态不能只包含我们讨论的是哪个子树，因为这并不能完整定义走到该子树的状态，我们还得看走到子树经过的点中有多少个点进行的是第二种操作，即该子树中元素被折半了多少次。
因此我们考虑以这两个变量作为我们动态规划的状态。但是这样我们状态会有多少个呢？如果不进行任何处理，我们的状态会达到 O(n²) ，因为总共有 n 个节点，深度可能达到 O(n)，因此此前折半数量有可能达到 O(n)。
但是，我们发现，每个节点的 coins[i] 不会超过 10⁴，因此在 14 次操作后总会变成 0，因此我们折半数量可以取与 14 的最小值，这样我们的状态总数便不超过 14n 了。
状态转移的过程中，我们只需要讨论当前节点选择的是何种操作，再往下进行答案的寻找即可，具体可见代码。如果你使用的是递归，要记得加上记忆化搜索，避免重复计算相同状态。每个状态的转移次数是 O(1) 的。因此，时间复杂度为 O(nlog⁡M)

class Solution:
    def maximumPoints(self, edges: List[List[int]], coins: List[int], k: int) -> int:
        n = len(coins)
        path = [[] for _ in range(n)]
        for u, v in edges:
            path[u].append(v)
            path[v].append(u)
        @cache
        def dfs(u, p, times):
            v = coins[u] >> times
            # 两种情况下的该点收益
            res0, res1 = v - k, v // 2
            # 折半情况下，新节点前的总折半次数，大于 14 和等于 14 等价
            new_times = min(times + 1, 14)
            for v in path[u]:
                if v != p:
                    res0 += dfs(v, u, times)
                    res1 += dfs(v, u, new_times)
            return max(res0, res1)
        ans = dfs(0, -1, 0)
        # 清空 cache 能让你的 Python 跑得快一点
        dfs.cache_clear()
        return ans