第 153 场双周赛-20250329
https://leetcode.cn/contest/biweekly-contest-153/
中国时间：2025-03-29 22:30, 1 小时 30 分
3498.字符串的反转度
implementation, https://leetcode.cn/problems/reverse-degree-of-a-string/
3499.操作后最大活跃区段数I
https://leetcode.cn/problems/maximize-active-section-with-trade-i/
3500.将数组分割为子数组的最小代价
https://leetcode.cn/problems/minimum-cost-to-divide-array-into-subarrays/
给你两个长度相等的整数数组 nums 和 cost，和一个整数 k。
你可以将 nums 分割成多个子数组。第 i 个子数组由元素 nums[l..r] 组成，其代价为：
(nums[0] + nums[1] + ... + nums[r] + k * i) * (cost[l] + cost[l + 1] + ... + cost[r])。
注意，i 表示子数组的顺序：第一个子数组为 1，第二个为 2，依此类推。
返回通过任何有效划分得到的 最小 总代价。
子数组 是一个连续的 非空 元素序列。
示例 1：
输入： nums = [3,1,4], cost = [4,6,6], k = 1
输出： 110
解释：
将 nums 分割为子数组 [3, 1] 和 [4] ，得到最小总代价。
- 第一个子数组
[3,1]的代价是(3 + 1 + 1 * 1) * (4 + 6) = 50。 - 第二个子数组
[4]的代价是(3 + 1 + 4 + 1 * 2) * 6 = 60。
示例 2：
输入： nums = [4,8,5,1,14,2,2,12,1], cost = [7,2,8,4,2,2,1,1,2], k = 7
输出： 985
解释：
将 nums 分割为子数组 [4, 8, 5, 1] ，[14, 2, 2] 和 [12, 1] ，得到最小总代价。
- 第一个子数组
[4, 8, 5, 1]的代价是(4 + 8 + 5 + 1 + 7 * 1) * (7 + 2 + 8 + 4) = 525。 - 第二个子数组
[14, 2, 2]的代价是(4 + 8 + 5 + 1 + 14 + 2 + 2 + 7 * 2) * (2 + 2 + 1) = 250。 - 第三个子数组
[12, 1]的代价是(4 + 8 + 5 + 1 + 14 + 2 + 2 + 12 + 1 + 7 * 3) * (1 + 2) = 210。
提示：
1 <= nums.length <= 1000cost.length == nums.length1 <= nums[i], cost[i] <= 10001 <= k <= 1000
3501.操作后最大活跃区段数II
https://leetcode.cn/problems/maximize-active-section-with-trade-ii/
给你一个长度为 n 的二进制字符串 s ，其中：
'1'表示一个 活跃 区域。'0'表示一个 非活跃 区域。
你最多可以进行一次 操作 来最大化 s 中活跃区间的数量。在一次操作中，你可以：
- 将一个被
'0'包围的连续'1'区域转换为全'0'。 - 然后，将一个被
'1'包围的连续'0'区域转换为全'1'。
此外，你还有一个 二维数组 queries，其中 queries[i] = [li, ri] 表示子字符串 s[li...ri]。
对于每个查询，确定在对子字符串 s[li...ri] 进行最优交换后，字符串 s 中 可能的最大 活跃区间数。
返回一个数组 answer，其中 answer[i] 是 queries[i] 的结果。
注意
- 对于每个查询，仅对
s[li...ri]处理时，将其看作是在两端都加上一个'1'后的字符串，形成t = '1' + s[li...ri] + '1'。这些额外的'1'不会对最终的活跃区间数有贡献。 - 各个查询相互独立。
示例 1：
输入： s = "01", queries = [[0,1]]
输出： [1]
解释：
因为没有被 '0' 包围的 '1' 区域，所以没有有效的操作可以进行。最大活跃区间数是 1。
示例 2：
输入： s = "0100", queries = [[0,3],[0,2],[1,3],[2,3]]
输出： [4,3,1,1]
解释：
- 查询
[0, 3]→ 子字符串"0100"→ 变为"101001"选择"0100"，"0100"→"0000"→"1111"。 最终字符串（去掉添加的'1'）为"1111"。最大活跃区间数为 4。 - 查询
[0, 2]→ 子字符串"010"→ 变为"10101"选择"010"，"010"→"000"→"111"。 最终字符串（去掉添加的'1'）为"1110"。最大活跃区间数为 3。 - 查询
[1, 3]→ 子字符串"100"→ 变为"11001"因为没有被'0'包围的'1'区域，所以没有有效的操作可以进行。最大活跃区间数为 1。 - 查询
[2, 3]→ 子字符串"00"→ 变为"1001"因为没有被'0'包围的'1'区域，所以没有有效的操作可以进行。最大活跃区间数为 1。
示例 3：
输入： s = "1000100", queries = [[1,5],[0,6],[0,4]]
输出： [6,7,2]
解释：
- 查询
[1, 5]→ 子字符串"00010"→ 变为"1000101"选择"00010"，"00010"→"00000"→"11111"。 最终字符串（去掉添加的'1'）为"1111110"。最大活跃区间数为 6。 - 查询
[0, 6]→ 子字符串"1000100"→ 变为"110001001"选择"000100"，"000100"→"000000"→"111111"。 最终字符串（去掉添加的'1'）为"1111111"。最大活跃区间数为 7。 - 查询
[0, 4]→ 子字符串"10001"→ 变为"1100011"因为没有被'0'包围的'1'区域，所以没有有效的操作可以进行。最大活跃区间数为 2。
示例 4：
输入： s = "01010", queries = [[0,3],[1,4],[1,3]]
输出： [4,4,2]
解释：
- 查询
[0, 3]→ 子字符串"0101"→ 变为"101011"选择"010"，"010"→"000"→"111"。 最终字符串（去掉添加的'1'）为"11110"。最大活跃区间数为 4。 - 查询
[1, 4]→ 子字符串"1010"→ 变为"110101"选择"010"，"010"→"000"→"111"。 最终字符串（去掉添加的'1'）为"01111"。最大活跃区间数为 4。 - 查询
[1, 3]→ 子字符串"101"→ 变为"11011"因为没有被'0'包围的'1'区域，所以没有有效的操作可以进行。最大活跃区间数为 2。
提示：
1 <= n == s.length <= 10^51 <= queries.length <= 10^5s[i]只有'0'或'1'。queries[i] = [li, ri]0 <= li <= ri < n
下面代码 超出时间限制，584 / 592
下面给出一种直观、易懂的解法思路（注意：下面的“朴素扫描”在候选区块数较少时能通过，若候选区块很多，则需要借助二维数据结构（例如 2D 线段树／树状数组）做区间查询以降低时间复杂度，但思路是一致的）。
思路说明
全局基础值
不论操作如何，由于操作仅修改 [l, r] 内的字符，整个字符串 s 的最终活跃区间数（这里定义为字符串中‘1’的总数）都会变为全局答案 = 原全局1的个数 + 操作在子串内带来的增量
其中“增量”只来自于对子串内的改变。对子串进行操作
给定查询 [l, r]，令子串为 sub = s[l...r]，在其两端加上额外的 '1' 得t = '1' + sub + '1'
操作要求必须同时做两步：
- 第一步：选择 t 内“被 0 包围的连续 1 区域”（注意要求该区块不能紧贴 t 两端）将其变为全 '0'
- 第二步：选择 t 内“被 1 包围的连续 0 区域”（同样要求区块内部，即不能包含 t 两端）将其变为全 '1'
分析可知，假设子串内原来的1的个数为 base_sub，那么若能在子串内选中一个候选的 1 区块，其左右两侧在子串内连续的 0 的个数分别记为 L_gain 和 R_gain（注意：由于查询时子串两侧本来没有‘0’（等价于加了“无贡献”的'1'），因此候选区块必须满足其左侧与右侧均存在至少一个 0，即候选 1 区块必须满足：
candidate 的起始位置 > l 且 candidate 的结束位置 < r
同时要求 s[candidate.start-1] == '0' 与 s[candidate.end+1] == '0'）。
那么对子串经过操作后，其1的个数将变为
base_sub + L_gain + R_gain
而整个 s 的1的个数最终为
total_ones + (L_gain + R_gain)
（因为 s 中原本子串部分贡献 base_sub，加上操作后多出的 L_gain+R_gain，且 s 其余部分不变）候选区块的预处理
预先遍历 s，找到所有连续1的区块，记录其左右边界。只有那些满足：- 该区块完全在 s 内部（即区块的起始位置 ≥ 1 且结束位置 ≤ n-2）
- 且该区块左右相邻的位置均为 '0'
的区块，才能作为候选区块参与操作。
同时，为了后续计算“在查询 [l,r] 内实际能获得的增量”，我们需要预处理 s 中连续 0 的信息： - 数组 L[i]：以 i 位置结尾的连续 0 的个数
- 数组 R[i]：从 i 位置开始的连续 0 的个数
对于一个候选区块，记其在 s 中的位置为 [a, b]（满足 a ≥ 1, b ≤ n-2，且 s[a-1] == '0'，s[b+1] == '0'）。
在任意查询 [l, r] 中，如果该候选区块落在子串内部（即要求 a ≥ l+1 且 b ≤ r-1），那么：- 左侧有效增量为：
left_gain = min( L[a-1]，a – l )
（因为从 a–1 往左连续的 0 数目可能超过 a – l，即查询区间内实际连续 0 数量为 a – l） - 右侧有效增量为：
right_gain = min( R[b+1]，r – b )
该候选区块在查询中的“增量”贡献即为 left_gain + right_gain。
查询答案
对于每个查询 [l, r]，我们在候选区块中只考虑那些满足a ≥ l+1 且 b ≤ r-1
的候选区块，然后取其 left_gain+right_gain 的最大值记为 gain_max（若不存在这样的候选区块，则 gain_max=0）。
最终答案 = 全局1的个数（原 s 中1的个数） + gain_max。
代码说明
下面代码中提供了一个朴素版本：
- 预处理 s 得到全局连续 0 长度数组 L 与 R
- 遍历 s 得到所有候选“1 区块”并存入列表 candidates，其中每个候选记录 (a, b, A, B) ，其中 A = L[a-1]、B = R[b+1]
- 对于每个查询 [l, r]，直接遍历 candidates（注意：候选数最多 O(n)）筛选出满足条件的候选，计算增量，并取最大值
- 最后答案 = total_ones + max_gain
注意：在最坏情况下候选区块数可能较多（例如 s 为“0 1 0 1 0 1 …”时），此朴素扫描每个查询的复杂度为 O(candidate_count)；如果查询数也较多，总复杂度可能达到 O(10^5 × candidate_count)；若候选较多（数万级），可能需要用二维数据结构加速查询。本代码给出的是最直观的写法，便于理解题意和操作步骤。
Python 代码
class Solution:
def maxActiveSectionsAfterTrade(self, s: str, queries: list) -> list:
n = len(s)
total_ones = s.count('1')
# 预处理：计算连续0的长度
L = [0] * n # L[i]：以 i 结尾的连续0数
if s[0] == '0':
L[0] = 1
for i in range(1, n):
if s[i] == '0':
L[i] = L[i-1] + 1
else:
L[i] = 0
R = [0] * n # R[i]：从 i 开始的连续0数
if s[n-1] == '0':
R[n-1] = 1
for i in range(n-2, -1, -1):
if s[i] == '0':
R[i] = R[i+1] + 1
else:
R[i] = 0
# 预处理：找出所有候选的“1区块”
# 候选区块要求：
# 1. 区块在 s 中连续的1，记作 [a, b]，且 a>=1, b<=n-2（确保有左右邻居）
# 2. s[a-1]=='0' 且 s[b+1]=='0'
candidates = []
i = 0
while i < n:
if s[i] == '1':
start = i
while i+1 < n and s[i+1] == '1':
i += 1
end = i
if start >= 1 and end <= n-2 and s[start-1] == '0' and s[end+1] == '0':
# 记录候选区块及其左右可用连续0长度
candidates.append((start, end, L[start-1], R[end+1]))
i += 1
else:
i += 1
# 对于每个查询 [l, r]，将子串 s[l...r]看作 t = '1' + s[l...r] + '1'
# 在 t 中只有当候选区块落在内部（即候选区块在 s 中的位置满足 a >= l+1 且 b <= r-1）
# 才能进行操作，并且在查询中的有效增量为：
# left_gain = min( L[a-1], a - l )
# right_gain = min( R[b+1], r - b )
# 候选区块贡献 = left_gain + right_gain
# 最终答案 = total_ones + max_{候选符合条件}(left_gain+right_gain)（如果没有候选，则答案为 total_ones）
ans = []
for l, r in queries:
gain_max = 0
# 注意：子串长度 m = r - l + 1，候选区块必须满足：a >= l+1 且 b <= r-1
for a, b, A, B in candidates:
if a >= l + 1 and b <= r - 1:
left_gain = min(A, a - l)
right_gain = min(B, r - b)
gain_max = max(gain_max, left_gain + right_gain)
ans.append(total_ones + gain_max)
return ans
# 示例测试
if __name__ == "__main__":
sol = Solution()
# 示例 1
s = "01"
queries = [[0, 1]]
print(sol.maxActiveSectionsAfterTrade(s, queries)) # 输出 [1]
# 示例 2
s = "0100"
queries = [[0,3],[0,2],[1,3],[2,3]]
print(sol.maxActiveSectionsAfterTrade(s, queries)) # 输出 [4,3,1,1]
# 示例 3
s = "1000100"
queries = [[1,5],[0,6],[0,4]]
print(sol.maxActiveSectionsAfterTrade(s, queries)) # 输出 [6,7,2]
# 示例 4
s = "01010"
queries = [[0,3],[1,4],[1,3]]
print(sol.maxActiveSectionsAfterTrade(s, queries)) # 输出 [4,4,2]说明
- 预处理部分先计算连续0的长度数组 L 与 R，然后扫描 s 得到所有候选“1区块”（要求区块两侧在 s 内均为 '0'）。
- 每个查询中，我们只检查候选区块是否“完全落在”子串内部（即要求 candidate.start ≥ l+1 且 candidate.end ≤ r-1）；若满足，则计算其在查询中的有效增量（左侧为 min( L[a-1], a – l )，右侧为 min( R[b+1], r – b )）。
- 最终答案即为全局 s 中1的个数（不受操作影响的部分）加上查询中能够获得的最大增量。
若后续候选区块数较多时，需要将候选区块按 a 或 b 建立二维数据结构来加速查询，本解法不再赘述。
这就是一种符合新题面要求的 Python 代码。