# # Leetcode 第231场周赛题解

## # Problem A - 检查二进制字符串字段 (opens new window)

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

class Solution {
public:
bool checkOnesSegment(string s) {
int ans = 0;
char last = '0';
for (char c : s) {
if (c == '1' && last == '0') {
ans++;
}
last = c;
}
return ans <= 1;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

## # Problem B - 构成特定和需要添加的最少元素 (opens new window)

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

typedef long long ll;

class Solution {
public:
int minElements(vector<int>& nums, int limit, int goal) {
ll sum = 0;
for (int num : nums)
sum += num;
ll delta = abs(sum - goal);
if (delta == 0)
return 0;
return (delta - 1) / limit + 1;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

## # Problem C - 从第一个节点出发到最后一个节点的受限路径数 (opens new window)

$N$开始跑一次单源Dijkstra，之后按照$dist$升序进行动态规划求解。

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

typedef long long ll;
const ll MOD = 1e9 + 7;

class Solution {
public:
int countRestrictedPaths(int n, vector<vector<int>>& edges) {
for (auto &edge : edges) {
int u = edge[0], v = edge[1], d = edge[2];
}
vector<int> dist(n + 1, INT_MAX);
dist[n] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.emplace(0, n);
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u])
continue;
for (auto [v, c] : adj[u]) {
if (d + c < dist[v]) {
dist[v] = d + c;
pq.emplace(dist[v], v);
}
}
}
vector<int> order(n);
for (int i = 0; i < n; ++i)
order[i] = i + 1;
sort(order.begin(), order.end(), [&](int u, int v) {
return dist[u] < dist[v];
});
vector<ll> ans(n + 1);
ans[n] = 1;
for (int u : order) {
for (auto [v, c] : adj[u]) {
if (dist[v] > dist[u]) {
ans[v] = (ans[v] + ans[u]) % MOD;
}
}
}
return ans[1];
}
};

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
38
39
40
41
42
43
44
45
46

## # Problem D - 使所有区间的异或结果为零 (opens new window)

• $a_1=a_{k+1}=a_{2k+1}=\dots$
• $a_2=a_{k+2}=a_{2k+2}=\dots$
• $\dots$

• $dp[0]=0$
• $dp[val]=\infty\ (val\neq0)$

1. 将当前组的数全都改为同一个值，此时不管我们之前如何选择，都可以利用这一个值的选择得到任何一个异或值，那么我们自然应该选择之前的代价中最小的那个，此时的代价为$size[i]+\min{dp[val]}$，新状态的异或值可以为$[0,2^D)$中的任意一个值。这一转移需要进行$K$次。
2. 使用当前组中的某一个值$val'$。此时我们需要枚举之前的异或值$val$（或枚举达到的目标值，二者是等价的），此时的代价为$size[i]-cnt[i][val']+dp[val]$，新状态的异或值为$val\oplus val'$。这一转移最多需要进行$N$次。
• 时间复杂度$\mathcal{O}(2^D\cdot(K+N))$。其中$D=10$
• 空间复杂度$\mathcal{O}(N + 2^D)$

const int INF = 0x3f3f3f3f;

class Solution {
public:
int minChanges(vector<int>& nums, int k) {
int n = nums.size();
vector<unordered_map<int, int>> groups(k);
vector<int> size(k);
for (int i = 0; i < k; ++i) {
for (int j = i; j < n; j += k) {
groups[i][nums[j]]++;
size[i]++;
}
}

vector<int> dp(1 << 10, INF);
dp[0] = 0;
for (int i = 0; i < k; ++i) {
int lo = *min_element(dp.begin(), dp.end());
vector<int> ndp(1 << 10, lo + size[i]);
for (int j = 0; j < (1 << 10); ++j) {
if (dp[j] == INF)
continue;
for (auto [p, freq] : groups[i]) {
int nxt = p ^ j;
ndp[nxt] = min(ndp[nxt], dp[j] + size[i] - freq);
}
}
dp = move(ndp);
}

return dp[0];
}
};

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