第 452 场周赛-20250601

https://leetcode.cn/contest/weekly-contest-452/

中国时间：2025-06-01 10:30, 1 小时 30 分

M3566.等积子集的划分方案

bitmask, https://leetcode.cn/problems/partition-array-into-two-equal-product-subsets/

M3567.子矩阵的最小绝对差

brute force, https://leetcode.cn/problems/minimum-absolute-difference-in-sliding-submatrix/

M3568.清理教室的最少移动

bfs, bitmask, https://leetcode.cn/problems/minimum-moves-to-clean-the-classroom/

T3569.分割数组后不同质数的最大数目

https://leetcode.cn/problems/maximize-count-of-distinct-primes-after-split/

给你一个长度为 'n' 的整数数组 nums，以及一个二维整数数组 queries，其中 queries[i] = [idx, val]。

对于每个查询：

1. 更新 nums[idx] = val。
2. 选择一个满足 1 <= k < n 的整数 k ，将数组分为非空前缀 nums[0..k-1] 和后缀 nums[k..n-1]，使得每部分中 不同 质数的数量之和 最大 。

注意：每次查询对数组的更改将持续到后续的查询中。

返回一个数组，包含每个查询的结果，按给定的顺序排列。

质数是大于 1 的自然数，只有 1 和它本身两个因数。

示例 1：

输入: nums = [2,1,3,1,2], queries = [[1,2],[3,3]]

输出: [3,4]

解释:

• 初始时 nums = [2, 1, 3, 1, 2]。
• 在第一次查询后，nums = [2, 2, 3, 1, 2]。将 nums 分为 [2] 和 [2, 3, 1, 2]。[2] 包含 1 个不同的质数，[2, 3, 1, 2] 包含 2 个不同的质数。所以此查询的答案是 1 + 2 = 3。
• 在第二次查询后，nums = [2, 2, 3, 3, 2]。将 nums 分为 [2, 2, 3] 和 [3, 2]，其答案为 2 + 2 = 4。
• 最终输出为 [3, 4]。

示例 2：

输入: nums = [2,1,4], queries = [[0,1]]

输出: [0]

解释:

• 初始时 nums = [2, 1, 4]。
• 在第一次查询后，nums = [1, 1, 4]。此时数组中没有质数，因此此查询的答案为 0。
• 最终输出为 [0]。

提示：

• 2 <= n == nums.length <= 5 * 10^4
• 1 <= queries.length <= 5 * 10^4
• 1 <= nums[i] <= 10^5
• 0 <= queries[i][0] < nums.length
• 1 <= queries[i][1] <= 10^5

class Solution:
    def maximumCount(self, nums: List[int], queries: List[List[int]]) -> List[int]: