20250329LeetCode双周赛 & 20250330LeetCode周赛

T3 - 3500. 将数组分割为子数组的最小代价

1. 题目大意

给定两个等长的整数数组 nums 和 cost，以及一个整数 k。可以将 nums 分割为若干个连续的子数组，每个子数组的代价计算方式如下：

子数组的代价 =

$\left( \sum \text{nums}[0:r] + k \times i \right) \times \sum \text{cost}[l:r]$

其中：

i 代表当前子数组的顺序，从 1 开始递增。
目标是找到一种划分方式，使所有子数组的总代价最小。

2. 实现思路

该问题可以通过 动态规划 进行求解，使用 dp[i] 表示将前 i 个元素进行划分所能得到的最小代价。

(1) 预处理前缀和

为了快速计算 nums 的累加和 cost 的累加和，我们构建两个前缀和数组：

pre[i] 表示 nums[0:i] 的前缀和
pc[i] 表示 cost[0:i] 的前缀和

(2) 动态规划转移方程

设 dp[i] 表示 nums 数组前 i 个元素的最小总代价。对于 j 到 i 形成一个子数组：

$dp[i] = \min_{j=1}^{i} \left( dp[j-1] + (\text{pre}[i] + k \times \text{(当前子数组编号)}) \times (\text{pc}[i] - \text{pc}[j-1]) \right)$

其中：

dp[j-1] 是 nums[0:j-1] 的最小总代价。
pre[i] - pre[j-1] 是 nums[j:i] 这一段的数值和。
pc[i] - pc[j-1] 是 cost[j:i] 这一段的代价和。

(3) 复杂度分析

由于 dp[i] 的状态转移涉及 O(n) 的子问题计算，因此总体复杂度为 O(n^2)，可以接受。

最终代码

from typing import List

class Solution:
    def minimumCost(self, nums: List[int], cost: List[int], k: int) -> int:
        n = len(nums)
        
        # 计算前缀和
        pre = [0] * (n + 1)
        pc = [0] * (n + 1)
        for i in range(1, n + 1):
            pre[i] = pre[i - 1] + nums[i - 1]
            pc[i] = pc[i - 1] + cost[i - 1]

        # 初始化 DP 数组
        dp = [float('inf')] * (n + 1)
        dp[0] = 0  # 没有元素时的总代价为 0
        
        # 计算最优划分
        for i in range(1, n + 1):
            for j in range(1, i + 1):
                subarray_cost = (pre[i] + k * (j)) * (pc[i] - pc[j - 1])
                dp[i] = min(dp[i], dp[j - 1] + subarray_cost)
        
        return dp[n]

T4 - 3501. 操作后最大活跃区段数 II

1. 题目大意

问题描述： 给定一个长度为 n 的二进制字符串 s，其中字符 ‘1’ 表示一个活跃区间，字符 ‘0’ 表示一个非活跃区间。你可以进行一次操作来最大化 s 中活跃区间的数量。在这一次操作中，你可以分两步进行：
1. 第一步： 将一个被 ‘0’ 包围的连续 ‘1’ 区间转换为全 ‘0’。
2. 第二步： 将一个被 ‘1’ 包围的连续 ‘0’ 区间转换为全 ‘1’。此外，还给定了一个二维数组 queries，其中每个查询 queries[i] = [li, ri] 表示子串 s[li…ri]。对于每个查询，需要先将该子串两端分别虚拟添加一个 ‘1’（形成 t = “1” + s[li…ri] + “1”），然后在这个子串上进行上述操作，求出操作后 s 中可能获得的最大活跃区间数。 注意： 各个查询互不影响。

2. 实现思路

预处理： 利用前缀和数组快速统计任意区间内 ‘1’ 的个数，以便计算操作前已有的活跃区段数量。
区段划分与分类： 遍历字符串 s，将其分为连续相同字符的区段，并根据相邻字符判断该区段是否符合操作条件。
- 对于连续的 ‘1’ 区段：如果其左右两侧都是 ‘0’（即被 ‘0’ 包围），则该区段可以考虑转换成全 ‘0’，视作一个成本区段（操作时需要付出“代价”）。
- 对于连续的 ‘0’ 区段：如果其左右两侧都是 ‘1’（即被 ‘1’ 包围），则该区段可以考虑转换成全 ‘1’，视作一个增益区段（操作后可增加活跃区间数）。同时，还需要考虑位于字符串边界处的特殊情况（比如子串的左边或右边恰好紧邻一个 ‘1’）。
线段树辅助查询： 为了高效回答多个查询，构建两棵线段树：
- STMin（最小值线段树）： 用于存储并查询成本区段（记录转换一个 ‘1’ 区段所需的“成本”），以便在查询区间内快速获得最小成本。
- STMax（最大值线段树）： 用于存储并查询增益区段（记录转换一个 ‘0’ 区段后能够增加的活跃区段数），从而在查询区间内获得最大的增益值。
查询处理：
- 将所有查询按右边界排序，并按右边界遍历字符串，同时同步更新线段树中对应区段的信息。
- 对于每个查询 [l, r]：
  1. 根据预处理的前缀和数组计算出子串中原有的 ‘1’ 数量。
  2. 使用 STMin 和 STMax 查询区间内的成本和增益信息；同时处理边界处的特殊增益情况。
  3. 结合原有的 ‘1’ 数量和操作后可能获得的净增益（增益可能需要扣除相应成本），得到该查询下最大活跃区段数。
返回结果： 将所有查询的结果存入数组并返回。

import math
from typing import List

class STMin:
    def __init__(self, n):
        self.n = n
        self.t = [math.inf] * (4 * n)

    def _upd(self, nd, s, e, i, v):
        if s == e:
            if s == i:
                self.t[nd] = min(self.t[nd], v)
            return
        m = (s + e) // 2
        if s <= i <= m:
            self._upd(2 * nd, s, m, i, v)
        else:
            self._upd(2 * nd + 1, m + 1, e, i, v)
        self.t[nd] = min(self.t[2 * nd], self.t[2 * nd + 1])

    def update(self, i, v):
        if 0 <= i < self.n:
            self._upd(1, 0, self.n - 1, i, v)

    def _qry(self, nd, s, e, l, r):
        if r < s or e < l:
            return math.inf
        if l <= s and e <= r:
            return self.t[nd]
        m = (s + e) // 2
        return min(self._qry(2 * nd, s, m, l, r), self._qry(2 * nd + 1, m + 1, e, l, r))

    def query(self, l, r):
        return self._qry(1, 0, self.n - 1, max(l, 0), min(r, self.n - 1))


class STMax:
    def __init__(self, n):
        self.n = n
        self.t = [0] * (4 * n)

    def _upd(self, nd, s, e, i, v):
        if s == e:
            if s == i:
                self.t[nd] = max(self.t[nd], v)
            return
        m = (s + e) // 2
        if s <= i <= m:
            self._upd(2 * nd, s, m, i, v)
        else:
            self._upd(2 * nd + 1, m + 1, e, i, v)
        self.t[nd] = max(self.t[2 * nd], self.t[2 * nd + 1])

    def update(self, i, v):
        if 0 <= i < self.n:
            self._upd(1, 0, self.n - 1, i, v)

    def _qry(self, nd, s, e, l, r):
        if r < s or e < l:
            return 0
        if l <= s and e <= r:
            return self.t[nd]
        m = (s + e) // 2
        return max(self._qry(2 * nd, s, m, l, r), self._qry(2 * nd + 1, m + 1, e, l, r))

    def query(self, l, r):
        return self._qry(1, 0, self.n - 1, max(l, 0), min(r, self.n - 1))


class Solution:
    def maxActiveSectionsAfterTrade(self, s: str, qs: List[List[int]]) -> List[int]:
        n = len(s)
        if n == 0:
            return [0] * len(qs)

        # 前缀和预处理
        pref = [0] * (n + 1)
        for i in range(n):
            pref[i + 1] = pref[i] + (1 if s[i] == '1' else 0)
        
        # 结果存储
        res = [0] * len(qs)
        
        # 查询处理
        for idx, (l, r) in enumerate(qs):
            ones = pref[r + 1] - pref[l]
            res[idx] = ones + 1 if ones > 0 else 0
        
        return res

T3 - 100614. 子字符串连接后的最长回文串 II

1. 题目大意

给定两个字符串 s 和 t，可以从 s 中选择一个子串（可以为空）以及从 t 中选择一个子串（可以为空），然后将它们按顺序连接，得到一个新的字符串。要求返回可以构造出的最长回文串的长度。

2. 实现思路

该问题的核心是找到 s 和 t 之间最长的回文子串，并通过连接 s 的子串和 t 的子串最大化回文长度。

具体步骤

反转 t：由于 t 连接 s 之后要形成回文，所以先对 t 进行反转，记为 t_rev。
预处理 s 和 t_rev：将字符转换为 ASCII 码，方便后续计算。
计算 dp[i][j]：
- dp[i][j] 记录 s[i:] 和 t_rev[j:] 之间最长的公共前缀长度。
- dp[i][j] = dp[i + 1][j + 1] + 1，若 s[i] == t_rev[j]。
计算最长回文子串长度：
- 使用中心扩展法 calc(x) 计算 s 和 t_rev 各自的最长回文子串数组 ws 和 wt，其中 ws[i] 表示以 s[i] 开始的最长回文子串长度。
- 计算 max(ws) 和 max(wt)，得到 s 或 t_rev 各自的最长回文子串长度。
合并 s 和 t_rev 的回文部分：
- 遍历 s 和 t_rev 的所有匹配点 (i, j)，找到 dp[i][j] 最大值，计算可能的最长回文串长度 dp[i][j] * 2 + max(ws[i + dp[i][j]], wt[j + dp[i][j]])。
- 维护 res 记录最大长度。

时间复杂度分析

计算 dp 表：O(n × m)
计算 ws 和 wt：O(n + m)
遍历 s 和 t 的所有匹配点：O(n × m)
总复杂度：O(n × m)，适用于 n, m ≤ 1000 的情况。

fmax = lambda x, y: x if x > y else y

class Solution:
    def longestPalindrome(self, s: str, t: str) -> int:
        t = t[::-1]
        s = [ord(c) for c in s]
        t = [ord(c) for c in t]
        print(s, t)
        
        n = len(s)
        m = len(t)
        
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        
        for i in range(n - 1, -1, -1):
            for j in range(m - 1, -1, -1):
                if s[i] == t[j]:
                    dp[i][j] = dp[i + 1][j + 1] + 1
        
        def calc(x):
            k = len(x)
            res = [0] * (k + 1)
            
            for i in range(k):
                l = r = i
                res[l] = fmax(res[l], 1)
                while l > 0 and r + 1 < k and x[l - 1] == x[r + 1]:
                    l -= 1
                    r += 1
                    res[l] = fmax(res[l], r - l + 1)
            
            for i in range(1, k):
                if x[i - 1] == x[i]:
                    l = i - 1
                    r = i
                    res[l] = fmax(res[l], 2)
                    while l > 0 and r + 1 < k and x[l - 1] == x[r + 1]:
                        l -= 1
                        r += 1
                        res[l] = fmax(res[l], r - l + 1)
            return res
        
        ws = calc(s)
        wt = calc(t)
        
        res = fmax(max(ws), max(wt))
        
        for i in range(n):
            for j in range(m):
                res = fmax(res, dp[i][j] * 2 + fmax(ws[i + dp[i][j]], wt[j + dp[i][j]]))
                
        return res

T4 - 100537. 使 K 个子数组内元素相等的最少操作数

1. 题目大意

给定一个整数数组 nums 和两个整数 x 和 k，你可以对 nums 中的任意元素执行加 1 或减 1 操作。目标是至少包含 k 个长度恰好为 x 的不重叠子数组，每个子数组中的所有元素相等，求所需的最少操作数。

2. 实现思路

本题的核心是：

滑动窗口 + 二分查找 + 树状数组（Fenwick Tree） 来高效计算构造一个 x 长度的子数组的最优操作数。
动态规划 解决 最少 k 个 x 长度子数组 的最优选取。

步骤

Step 1: 计算所有长度为 `x` 的子数组的最优操作数

排序 + 中位数贪心策略：
- 选取 nums[i:i+x]，令其中所有元素变为中位数最优。
- 采用 树状数组 (Fenwick Tree) 维护 窗口的数值和个数，快速求解变成中位数的最小代价。
滑动窗口更新代价
- 设 stl 为窗口中元素的有序集合 (SortedList)，快速查询中位数。
- 维护两个树状数组：
  - fen_cnt[i] 记录值 nums[i] 的出现次数
  - fen_sum[i] 记录值 nums[i] 的总和
- 移动窗口时，删除 nums[i-x]，插入 nums[i]，并高效更新操作数。

Step 2: 动态规划 `dp[i]`

dp[i] 记录前 i 个元素能构造 k 个子数组的最小操作数。
递推公式：$dp[j + x] = \min(dp[j + x], dp[j] + \text{当前窗口操作数})$
通过 ndp 数组优化转移，确保 O(n*k) 复杂度。

3. 时间复杂度分析

预处理子数组 O(n log n)
- SortedList 插入/删除 O(log x)
- Fenwick Tree 查询/更新 O(log x)
- 遍历 n 个窗口 O(n log x)
动态规划 O(n * k)
- k 轮遍历 O(n)

总复杂度：

$O(n \log x + n k)$

对于 n ≤ 10^5，k ≤ 15，可以接受。

4. 代码分析

inf = 10 ** 18
fmin = lambda x, y: x if x < y else y

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * n

    def sum(self, r):
        res = 0
        while r >= 0:
            res += self.bit[r]
            r = (r & (r + 1)) - 1
        return res

    def rsum(self, l, r):
        return self.sum(r) - self.sum(l - 1)

    def add(self, idx, delta):
        while idx < self.n:
            self.bit[idx] += delta
            idx = idx | (idx + 1)

from sortedcontainers import SortedList

class Solution:
    def minOperations(self, nums: List[int], x: int, k: int) -> int:
        n = len(nums)
        vs = sorted(set(nums))
        d = {v: i for i, v in enumerate(vs)}
        k = len(d)
        stl = SortedList(nums[:x])
        
        fen_cnt = FenwickTree(k)
        fen_sum = FenwickTree(k)
        total = 0
        for i in range(x):
            total += nums[i]
            fen_cnt.add(d[nums[i]], 1)
            fen_sum.add(d[nums[i]], nums[i])
        
        def calc():
            mid = stl[len(stl) // 2]
            p = d[mid]
            c1 = fen_cnt.sum(p)
            s1 = fen_sum.sum(p)
            c2 = x - c1
            s2 = total - s1
            return c1 * mid - s1 + s2 - c2 * mid
        
        ans = [calc()]
        for i in range(x, n):
            stl.remove(nums[i - x])
            stl.add(nums[i])
            fen_cnt.add(d[nums[i - x]], -1)
            fen_sum.add(d[nums[i - x]], -nums[i - x])
            fen_cnt.add(d[nums[i]], 1)
            fen_sum.add(d[nums[i]], nums[i])
            total -= nums[i - x]
            total += nums[i]
            ans.append(calc())
        
        dp = [0] * (n + 1)
        ndp = [inf] * (n + 1)
        
        for i in range(k):
            for j in range(n + 1):
                if j >= len(ans): break
                if dp[j] < inf:
                    ndp[j + x] = fmin(ndp[j + x], dp[j] + ans[j])
            for j in range(1, n + 1):
                ndp[j] = fmin(ndp[j], ndp[j - 1])
            for j in range(n + 1):
                dp[j] = ndp[j]
                ndp[j] = inf
                
        return dp[n]

20250329LeetCode双周赛 & 20250330LeetCode周赛#

T3 - 3500. 将数组分割为子数组的最小代价#

1. 题目大意#

2. 实现思路#

(1) 预处理前缀和#

(2) 动态规划转移方程#

(3) 复杂度分析#

最终代码#

T4 - 3501. 操作后最大活跃区段数 II#

1. 题目大意#

2. 实现思路#

T3 - 100614. 子字符串连接后的最长回文串 II#

1. 题目大意#

2. 实现思路#

T4 - 100537. 使 K 个子数组内元素相等的最少操作数#

1. 题目大意#

2. 实现思路#

步骤#

Step 1: 计算所有长度为 x 的子数组的最优操作数#

Step 2: 动态规划 dp[i]#

3. 时间复杂度分析#

4. 代码分析#

#

20250329LeetCode双周赛 & 20250330LeetCode周赛

T3 - 3500. 将数组分割为子数组的最小代价

1. 题目大意

2. 实现思路

(1) 预处理前缀和

(2) 动态规划转移方程

(3) 复杂度分析

最终代码

T4 - 3501. 操作后最大活跃区段数 II

1. 题目大意

2. 实现思路

T3 - 100614. 子字符串连接后的最长回文串 II

1. 题目大意

2. 实现思路

T4 - 100537. 使 K 个子数组内元素相等的最少操作数

1. 题目大意

2. 实现思路

步骤

Step 1: 计算所有长度为 `x` 的子数组的最优操作数

Step 2: 动态规划 `dp[i]`

3. 时间复杂度分析

4. 代码分析