# Leetcode 第329场周赛题解

# Problem A - 交替数字和 (opens new window)

# 方法一：模拟

• 时间复杂度 $\mathcal{O}(\log N)$
• 空间复杂度 $\mathcal{O}(1)$

class Solution:
def alternateDigitSum(self, n: int) -> int:
return sum((1 - i % 2 * 2) * d for i, d in enumerate(map(int, str(n))))

1
2
3

# Problem B - 根据第 K 场考试的分数排序 (opens new window)

# 方法一：排序

• 时间复杂度 $\mathcal{O}(N\log N)$
• 空间复杂度 $\mathcal{O}(NM)$

class Solution:
def sortTheStudents(self, score: List[List[int]], k: int) -> List[List[int]]:
return sorted(score, key=lambda x: -x[k])

1
2
3

# Problem C - 执行逐位运算使字符串相等 (opens new window)

# 方法一：找规律

• 时间复杂度 $\mathcal{O}(N)$
• 空间复杂度 $\mathcal{O}(1)$

class Solution:
def makeStringsEqual(self, s: str, target: str) -> bool:
return s == target or ('1' in s and '1' in target)

1
2
3

# Problem D - 拆分数组的最小代价 (opens new window)

# 方法一：朴素动态规划

• 时间复杂度 $\mathcal{O}(N^2)$
• 空间复杂度 $\mathcal{O}(N^2)$

class Solution:
def minCost(self, nums: List[int], k: int) -> int:
n = len(nums)
c = [[0] * n for _ in range(n)]
dp = [int(1e18)] * n
dp[0] = k
c[0][nums[0]] = 1
for i in range(1, n):
dp[i] = min(dp[:i]) + k
num = nums[i]
c[i][num] = 1
for j in range(i):
c[j][num] += 1
if c[j][num] == 2:
dp[j] += 2
elif c[j][num] > 2:
dp[j] += 1
return min(dp)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 方法二：线段树（区间加，区间最小值）优化

• 时间复杂度 $\mathcal{O}(N\log N)$
• 空间复杂度 $\mathcal{O}(N)$

#include <atcoder/lazysegtree>

using ll = long long;
using S = ll;
using F = ll;

S op(S a, S b) { return min(a, b); }
S e() { return 1e18; }
S mapping(F f, S x) { return f + x; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }

class Solution {
public:
int minCost(vector<int>& nums, int k) {
int n = nums.size();
atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(n);
unordered_map<int, vector<int>> pos;
seg.set(0, k);
pos[nums[0]].push_back(0);
for (int i = 1; i < n; ++i) {
int num = nums[i];
seg.set(i, seg.prod(0, i) + k);
auto& p = pos[num];
int m = p.size();
if (m >= 2) {
seg.apply(0, p[m - 2] + 1, 1);
seg.apply(p[m - 2] + 1, p[m - 1] + 1, 2);
} else if (m == 1) {
seg.apply(0, p[0] + 1, 2);
}
p.push_back(i);
}

return seg.all_prod();
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37