第 463 场周赛（GPT-3，Me-1）

发布于：2025-08-19 ⋅ 阅读:(18) ⋅ 点赞:(0)

不得不惊叹Deepseek 和 Kimi的算法能力了！

题目重述

给你一个整数数组 nums 和一个整数 k。你可以多次选择连续子数组 nums，其元素和可以被 k 整除，并将其删除；每次删除后，剩余元素会填补空缺。返回在执行任意次数此类删除操作后，nums 的最小可能和。

示例

假设输入：

nums = [1, 2, 3, 4, 5], k = 3

可能的删除操作：

  • 删除子数组 [3]（和为3，可被3整除），剩余 [1, 2, 4, 5]。
  • 删除子数组 [1, 2]（和为3，可被3整除），剩余 [3, 4, 5]，然后可以删除 [3]，剩余 [4, 5]。
  • 删除子数组 [2, 1]（注意：子数组必须连续，这里 [2, 1] 不是连续的，不可行）。
  • 删除子数组 [4, 5]（和为9，可被3整除），剩余 [1, 2, 3]，然后可以删除 [3]，剩余 [1, 2]。

看起来最小的和可能是 1 + 2 = 3。

解题思路

关键观察

要最小化剩余数组的和，我们需要尽可能多地删除和为 k 的倍数的连续子数组。这类似于从数组中删除一些元素，使得剩余元素的和最小。

动态规划

我们可以使用动态规划来解决这个问题。定义 dp[i] 为前 i 个元素（即 nums[0..i-1]）的最小剩余和。

状态转移

对于每个 i，我们有两种选择：

  1. 不删除任何以 i 结尾的子数组：dp[i] = dp[i-1] + nums[i-1]。
  2. 删除某个以 i 结尾的子数组 nums[j..i-1]，其中 sum(nums[j..i-1]) % k == 0。此时 dp[i] = dp[j]。

因此，状态转移方程为：

dp[i] = min(dp[i-1] + nums[i-1], min_{j < i and sum(nums[j..i-1]) % k == 0} dp[j])
优化求和

直接计算 sum(nums[j..i-1]) 的时间复杂度是 O(n^2)，对于较大的 n 会超时。我们可以用前缀和来优化：

  • 定义前缀和数组 prefix，其中 prefix[i] = sum(nums[0..i-1])。
  • 则 sum(nums[j..i-1]) = prefix[i] - prefix[j]。
  • 条件 sum(nums[j..i-1]) % k == 0 等价于 (prefix[i] - prefix[j]) % k == 0，即 prefix[i] % k == prefix[j] % k。

因此，我们可以用哈希表记录每个余数 r 对应的最小 dp[j]，其中 prefix[j] % k == r。

初始化
  • dp[0] = 0（前0个元素的和为0）。
  • prefix[0] = 0。
算法步骤
  1. 初始化 dp 数组，dp[0] = 0。
  2. 计算前缀和 prefix[i]。
  3. 使用哈希表 mod_map 记录余数 r 对应的最小 dp[j]。
    • 初始时 mod_map[0] = 0（对应 prefix[0] = 0）。
  4. 对于每个 i 从 1 到 n：
    • 计算当前前缀和 prefix[i] 和余数 r = prefix[i] % k。
    • 如果 r 在 mod_map 中存在，则 dp[i] = min(dp[i-1] + nums[i-1], mod_map[r])。
    • 否则 dp[i] = dp[i-1] + nums[i-1]。
    • 更新 mod_map[r] = min(mod_map.get(r, inf), dp[i])（确保存储的是最小的 dp[j]）。

代码实现

from typing import List

class Solution:
    def minSumAfterDeletion(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [0] * (n + 1)
        prefix = [0] * (n + 1)
        mod_map = {0: 0}  # 余数 -> 最小的dp[j]
        
        for i in range(1, n + 1):
            prefix[i] = prefix[i - 1] + nums[i - 1]
            r = prefix[i] % k
            if r in mod_map:
                dp[i] = min(dp[i - 1] + nums[i - 1], mod_map[r])
            else:
                dp[i] = dp[i - 1] + nums[i - 1]
            # 更新mod_map[r]为dp[i]和mod_map[r]的较小值
            if r in mod_map:
                mod_map[r] = min(mod_map[r], dp[i])
            else:
                mod_map[r] = dp[i]
        
        return dp[n]

示例验证

以 nums = [1, 2, 3, 4, 5], k = 3 为例：

初始化：

  • dp = [0, 0, 0, 0, 0, 0]
  • prefix = [0, 0, 0, 0, 0, 0]
  • mod_map = {0: 0}

计算 i = 1：

  • nums[0] = 1
  • prefix[1] = 1
  • r = 1 % 3 = 1
  • mod_map 中没有 1，所以 dp[1] = dp[0] + 1 = 1
  • mod_map = {0: 0, 1: 1}

计算 i = 2：

  • nums[1] = 2
  • prefix[2] = 1 + 2 = 3
  • r = 3 % 3 = 0
  • mod_map 中有 0，所以 dp[2] = min(dp[1] + 2, mod_map[0]) = min(1 + 2, 0) = 0
  • mod_map[0] 更新为 min(0, 0) = 0，mod_map = {0: 0, 1: 1}

计算 i = 3：

  • nums[2] = 3
  • prefix[3] = 3 + 3 = 6
  • r = 6 % 3 = 0
  • mod_map 中有 0，所以 dp[3] = min(dp[2] + 3, mod_map[0]) = min(0 + 3, 0) = 0
  • mod_map[0] 更新为 min(0, 0) = 0，mod_map = {0: 0, 1: 1}

计算 i = 4：

  • nums[3] = 4
  • prefix[4] = 6 + 4 = 10
  • r = 10 % 3 = 1
  • mod_map 中有 1，所以 dp[4] = min(dp[3] + 4, mod_map[1]) = min(0 + 4, 1) = 1
  • mod_map[1] 更新为 min(1, 1) = 1，mod_map = {0: 0, 1: 1}

计算 i = 5：

  • nums[4] = 5
  • prefix[5] = 10 + 5 = 15
  • r = 15 % 3 = 0
  • mod_map 中有 0，所以 dp[5] = min(dp[4] + 5, mod_map[0]) = min(1 + 5, 0) = 0
  • mod_map[0] 更新为 min(0, 0) = 0，mod_map = {0: 0, 1: 1}

最终 dp[5] = 0，表示可以删除所有元素，和为 0。这与直觉一致：

  • 删除 [1, 2]（和为3），剩余 [3, 4, 5]。
  • 删除 [3]（和为3），剩余 [4, 5]。
  • 删除 [4, 5]（和为9），剩余 []。

然而，题目描述似乎暗示“删除”是选择连续子数组并将其移除，剩余元素会填补空缺，但“最小可能和”是剩余元素的和。因此，0 是正确的。

修正理解

可能的误解：题目描述“删除连续子数组”后，剩余元素填补空缺，但“最小可能和”是剩余元素的和。因此，可以删除所有可能的子数组，使得剩余和最小。

因此，动态规划的方法是合理的。
2.
为了解决这个问题，我们需要高效地处理多个区间乘法查询，并在所有查询完成后计算数组所有元素的按位异或结果。由于直接模拟每个查询的更新操作会导致超时（时间复杂度为O(n*q)），我们采用根号分治策略，将查询分为大步长（k > sqrt(n)）和小步长（k <= sqrt(n)）两类，分别处理，以优化时间复杂度。

方法思路

  1. 问题分析：

    • 给定数组nums和查询数组queries，每个查询指定一个区间[l_i, r_i]、步长k_i和乘数v_i。
    • 对于每个查询，从l_i开始，以步长k_i遍历区间，将每个位置的元素乘以v_i并取模。
    • 最终返回数组所有元素的异或结果。

  2. 根号分治：

    • 大步长查询（k > sqrt(n)）：每个查询修改的位置数不超过sqrt(n)，直接暴力更新。
    • 小步长查询（k <= sqrt(n)）：按步长k分组，对每个k的同余类（模k余数相同的序列）使用差分数组处理区间乘法。

  3. 处理零值查询：

    • 若v_i = 0，则标记覆盖的位置为零，最终这些位置的结果为0。
    • 非零查询通过差分数组记录乘法因子，最后计算前缀积。

  4. 最终计算：

    • 对每个位置，若被零查询覆盖则结果为0；否则，结果为初始值、小步长乘法因子和大步长乘法因子的乘积取模。
    • 所有位置的结果进行异或运算。

解决代码

import math
from collections import defaultdict

MOD = 10**9 + 7

class Solution:
    def solve(self, nums, queries):
        n = len(nums)
        if n == 0:
            return 0
        B = int(math.isqrt(n)) + 1
        
        zero = [False] * n
        small_mul = [1] * n
        big_mul = [1] * n
        
        big_queries = []
        small_queries = []
        
        for query in queries:
            l, r, k, v = query
            if k > B:
                big_queries.append((l, r, k, v))
            else:
                small_queries.append((l, r, k, v))
                
        for l, r, k, v in big_queries:
            if v == 0:
                idx = l
                while idx <= r:
                    zero[idx] = True
                    idx += k
            else:
                idx = l
                while idx <= r:
                    big_mul[idx] = (big_mul[idx] * v) % MOD
                    idx += k
                    
        queries_by_k = defaultdict(list)
        for l, r, k, v in small_queries:
            queries_by_k[k].append((l, r, v))
            
        for k, q_list in queries_by_k.items():
            diff_mul_list = []
            diff_cover_list = []
            len_list = []
            for r in range(k):
                if r >= n:
                    len_r = 0
                else:
                    len_r = (n - 1 - r) // k + 1
                len_list.append(len_r)
                diff_mul_list.append([1] * (len_r + 1))
                diff_cover_list.append([0] * (len_r + 1))
                
            for l, r, v in q_list:
                r0 = l % k
                if r0 >= n:
                    continue
                start_idx = (l - r0) // k
                len_r = len_list[r0]
                if start_idx >= len_r:
                    continue
                end_idx = (r - r0) // k
                if end_idx >= len_r:
                    end_idx = len_r - 1
                else:
                    end_idx = min(end_idx, len_r - 1)
                    
                if v != 0:
                    diff_mul = diff_mul_list[r0]
                    diff_mul[start_idx] = (diff_mul[start_idx] * v) % MOD
                    if end_idx + 1 < len_r + 1:
                        inv_v = pow(v, MOD - 2, MOD)
                        diff_mul[end_idx + 1] = (diff_mul[end_idx + 1] * inv_v) % MOD
                else:
                    diff_cover = diff_cover_list[r0]
                    diff_cover[start_idx] += 1
                    if end_idx + 1 < len_r + 1:
                        diff_cover[end_idx + 1] -= 1
                        
            for r in range(k):
                len_r = len_list[r]
                if len_r == 0:
                    continue
                diff_mul = diff_mul_list[r]
                prod = [1] * len_r
                cur = 1
                for i in range(len_r):
                    cur = (cur * diff_mul[i]) % MOD
                    prod[i] = cur
                    
                diff_cover = diff_cover_list[r]
                cover_sum = 0
                cover_arr = [0] * len_r
                for i in range(len_r):
                    cover_sum += diff_cover[i]
                    cover_arr[i] = cover_sum
                    
                for i in range(len_r):
                    pos = r + i * k
                    if pos >= n:
                        break
                    if cover_arr[i] > 0:
                        zero[pos] = True
                    else:
                        small_mul[pos] = (small_mul[pos] * prod[i]) % MOD
                        
        res = 0
        for i in range(n):
            if zero[i]:
                total = 0
            else:
                total = nums[i] * small_mul[i] % MOD
                total = total * big_mul[i] % MOD
            res ^= total
            
        return res

方法解释

  1. 初始化：

    • 设置阈值B = sqrt(n) + 1，用于区分大步长和小步长查询。
    • 初始化zero数组标记被零查询覆盖的位置，small_mul和big_mul数组分别记录小步长和大步长查询的乘法因子。

  2. 查询分类：

    • 将查询按步长k分为大步长（k > B）和小步长（k <= B）两类。

  3. 处理大步长查询：

    • 对每个大步长查询，若v_i = 0，则遍历所有覆盖位置并标记zero数组；否则，更新big_mul数组。

  4. 处理小步长查询：

    • 按步长k分组，对每组中的每个同余类（模k余数相同的序列）初始化差分数组。
    • 对每个查询，若v_i = 0，更新差分覆盖数组；否则，更新差分乘法数组（使用乘法逆元处理区间结束）。
    • 计算前缀积和前缀和，更新small_mul和zero数组。

  5. 结果计算：

    • 遍历每个位置，若被零查询覆盖则结果为0；否则，计算初始值与乘法因子的乘积取模。
    • 所有位置的结果进行异或运算，返回最终结果。

该方法的时间复杂度为O(n * sqrt(n))，空间复杂度为O(n)，能高效处理大规模数据。

小步长查询处理算法详解（k ≤ √n）

该算法利用分组+同余类+差分数组的思想高效处理区间乘法查询，核心是通过数学变换将区间操作转化为单点操作，最后通过前缀计算得到最终结果。

算法步骤：

  1. 分组处理：

    • 将步长 k ≤ √n 的查询按 k 值分组
    • 对每个 k 值独立处理其所有查询

  2. 同余类分解：

    • 对每个 k 值，将数组分为 k 个同余类（余数 0 到 k-1）
    • 例如 k=3 时：
      • 余数0类：下标 0, 3, 6, 9, …
      • 余数1类：下标 1, 4, 7, 10, …
      • 余数2类：下标 2, 5, 8, 11, …

  3. 差分数组构建（每类两个差分数组）：

    • diff_mul：乘法操作的差分数组
      • 初始化为全1（乘法单位元）
      • 区间 [L,R] 乘以 v → L 位置乘 v，R+1 位置乘 v⁻¹（模逆元）
    • diff_cover：零覆盖标记的差分数组
      • 初始化为全0
      • 区间 [L,R] 置零 → L 位置+1，R+1 位置-1

  4. 查询转换（原下标→同余类下标）：

    • 对于查询 [l, r, k, v]：
      • 余数 r₀ = l % k
      • 在余数 r₀ 类中的起始位置：start_idx = (l - r₀) // k
      • 结束位置：end_idx = (r - r₀) // k（需边界检查）

  5. 前缀计算（处理每个同余类）：

    • 计算 diff_mul 的前缀积 → 得到每个位置的累积乘积
    • 计算 diff_cover 的前缀和 → 标记被零覆盖的位置

  6. 更新原数组：

    • 遍历每个位置：
      • 若被零覆盖 → 标记 zero[i] = True
      • 否则 → 将累积乘积乘到 small_mul[i]
关键技巧：

  1. 乘法逆元撤销操作：

    inv_v = pow(v, MOD-2, MOD)  # 费马小定理求逆元
    • 在 R+1 位置乘以逆元，确保只在 [L,R] 区间生效

  2. 零查询特殊处理：

    • 使用独立的覆盖标记数组
    • 优先级高于乘法操作

  3. 空间优化：

    • 不实际创建子序列数组
    • 通过索引映射直接操作原数组
时间复杂度分析：
  • 分组：O(q)
  • 每类查询处理：O(查询数量)
  • 每类前缀计算：O(n/k)
  • 总复杂度：O(k × n/k) = O(n) 每 k 值 → O(n√n)
示例说明：

假设 n=6，k=2，查询：[[1, 5, 2, 3]]

  1. 同余类分解：

    • 余数0类：下标 0, 2, 4 → 子序列 [a0, a2, a4]
    • 余数1类：下标 1, 3, 5 → 子序列 [a1, a3, a5]

  2. 查询转换：

    • l=1, r=5 → 余数 r₀=1
    • 在余数1类：start_idx=(1-1)//2=0, end_idx=(5-1)//2=2

  3. 差分数组操作：

    • diff_mul[0] *= 3
    • diff_mul[3] *= 3⁻¹（实际忽略，因超出范围）

  4. 前缀计算：

    • 前缀积：[3, 3, 3]（子序列所有位置乘以3）

  5. 更新原数组：

    • a1, a3, a5 的 small_mul 乘以3
优势：
  • 将区间操作转化为O(1)的差分操作
  • 通过分组控制总复杂度在O(n√n)
  • 完美处理零值查询的特殊情况
  • 利用模逆元实现乘法操作的精确撤销

这种设计巧妙结合了数论（逆元）、分组处理（根号分治）和差分数组技巧，是处理此类区间更新问题的经典范式。
6.


```cpp
class Solution {
public:
    long long maxProfit(vector<int>& prices, vector<int>& strategy, int k) {
        int n = prices.size();
        vector<long long> nums1(n,0);
        vector<long long> nums2(n,0);
        nums1[0] = prices[0];
        for (int i = 1;i < n;i ++) {
            nums1[i] = nums1[i-1]+prices[i];
        }
        long long nums_mon = 0;
        nums2[0] = prices[0] * strategy[0];
        nums_mon = nums2[0];
        for (int i = 1;i < n;i ++) {
            nums2[i] = nums2[i-1]+prices[i]*strategy[i];
            nums_mon += prices[i]*strategy[i];
        }
        long long ans = nums_mon;
        for (int i = k/2;i + k/2 -1 < n;i ++) {
            long long tmp = (nums1[i+k/2-1]-nums1[i-1]) + (nums2[n-1]-nums2[i+k/2-1]) ;
            if (i >= k/2+1)
                tmp += nums2[i-k/2-1];
            ans = max(ans,tmp);
        }
        return ans;
    }
};

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布