# # 2022年力扣杯春季赛个人赛题解

## # Problem A - 宝石补给 (opens new window)

### # 方法一：模拟

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

class Solution:
def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:
for u, v in operations:
amt = gem[u] // 2
gem[u] -= amt
gem[v] += amt
return max(gem) - min(gem)

1
2
3
4
5
6
7

## # Problem B - 烹饪料理 (opens new window)

### # 方法一：枚举

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

class Solution:
def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:
n = len(cookbooks)
ans = -1
for i in range(1, 1 << n):
s = [0] * 5
x = 0
y = 0
for j in range(n):
if (i & (1 << j)) != 0:
s = [si + mi for si, mi in zip(s, cookbooks[j])]
x += attribute[j][0]
y += attribute[j][1]
if y >= limit and all(si <= mi for si, mi in zip(s, materials)):
ans = max(ans, x)
return ans

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

## # Problem C - 黑白翻转棋 (opens new window)

### # 方法一：中序遍历 + 线段树

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

struct SegmentTreeNode {
int data = 0, l = 0, r = 0;
bool lazy = false;

void combine(SegmentTreeNode other) {
data = max(data, other.data);
}

inline void reset() {
data = 0;
lazy = false;
}
};

class SegmentTree {
int n;
vector<SegmentTreeNode> nodes;

void calc(int idx) {
nodes[idx].reset();
nodes[idx].combine(nodes[idx << 1]);
nodes[idx].combine(nodes[idx << 1 | 1]);
}

void build(int idx, int l, int r) {
nodes[idx].l = l, nodes[idx].r = r;
if (l == r)
nodes[idx].data = 0;
else {
int mid = (l + r) >> 1;
build(idx << 1, l, mid);
build(idx << 1 | 1, mid + 1, r);
calc(idx);
}
}

void push_down(int idx) {
if (!nodes[idx].lazy)
return;
for (int i = idx << 1; i <= (idx << 1 | 1); ++i) {
nodes[i].data = max(nodes[i].data, nodes[idx].data);
nodes[i].lazy = true;
}
nodes[idx].lazy = false;
}

public:
explicit SegmentTree(int n) {
this->n = n;
nodes = vector<SegmentTreeNode>((n + 1) << 2);
}

void init() { build(1, 1, n); }

void update(int idx, int l, int r, int x) {
if (l <= nodes[idx].l && r >= nodes[idx].r) {
nodes[idx].data = x;
nodes[idx].lazy = true;
} else {
push_down(idx);
int mid = (nodes[idx].l + nodes[idx].r) >> 1;
if (l <= mid)
update(idx << 1, l, r, x);
if (r > mid)
update(idx << 1 | 1, l, r, x);
calc(idx);
}
}

SegmentTreeNode query(int idx, int l, int r) {
if (l <= nodes[idx].l && r >= nodes[idx].r)
return nodes[idx];
push_down(idx);
SegmentTreeNode ans;
int mid = (nodes[idx].l + nodes[idx].r) >> 1;
if (l <= mid)
ans.combine(query(idx << 1, l, r));
if (r > mid)
ans.combine(query(idx << 1 | 1, l, r));
return ans;
}
};

class Solution {
vector<int> v;

void dfs(TreeNode *u) {
if (u == nullptr)
return;

dfs(u->left);
v.push_back(u->val);
dfs(u->right);
}
public:
int getNumber(TreeNode* root, vector<vector<int>>& ops) {
dfs(root);
unordered_map<int, int> mp;

for (int i = 0; i < v.size(); ++i)
mp[v[i]] = i + 1;

int n = v.size();
SegmentTree st(n);
st.init();
for (int i = 0; i < ops.size(); ++i) {
int l = mp[ops[i][1]], r = mp[ops[i][2]];
st.update(1, l, r, i + 1);
}

int ans = 0;
for (int i = 1; i <= n; ++i) {
int t = st.query(1, i, i).data;
if (t > 0 && ops[t - 1][0] == 1)
ans++;
}

return ans;
}
};

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

## # Problem D - 守护太空城 (opens new window)

### # 方法一：状态压缩动态规划

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

const int INF = 0x3f3f3f3f;
const int T[6] = {1, 3, 9, 27, 81, 243};

class Solution {
public:
int defendSpaceCity(vector<int>& time, vector<int>& position) {
int N = 0;
for (int pi : position)
N = max(N, pi);
N++;
vector<int> status(N + 1);
int K = 1;
for (int i = 0; i < time.size(); ++i) {
K = max(K, time[i]);
int t = time[i] - 1;
int p = position[i] + 1;
status[p] |= 1 << t;
}

vector<int> cost(T[K]), my(T[K]), nxt(T[K]);
vector<vector<int>> op(T[K]);
for (int i = 0; i < T[K]; ++i) {
int last = 0;
int now = i;
for (int k = 0; k < K; ++k) {
int curr = now % 3;
op[i].push_back(curr);
if (curr > 0)
my[i] |= 1 << k;
if (curr == 2)
nxt[i] |= 1 << k;
now /= 3;
if (curr != last) {
if (curr > 0)
cost[i] += curr + 1;
} else {
if (curr > 0)
cost[i]++;
}
last = curr;
}
}

vector<int> dp(1 << K, INF);
dp[0] = 0;
for (int i = 1; i <= N; ++i) {
vector<int> ndp(1 << K, INF);
for (int last = 0; last < (1 << K); ++last) {
if (dp[last] == INF)
continue;
for (int j = 0; j < T[K]; ++j) {
if (last & my[j])
continue;
if (i == N && nxt[j] > 0)
continue;
int cover = last | my[j];
if ((cover | status[i]) != cover)
continue;

ndp[nxt[j]] = min(ndp[nxt[j]], dp[last] + cost[j]);
}
}

dp = move(ndp);
}

return *min_element(dp.begin(), dp.end());
}
};

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

## # Problem E - 夺回据点 (opens new window)

### # 方法一：找出割点，然后分别处理每个连通块

• 抛弃掉同时与多个割点相连的连通块。
• 求出剩余的连通块中的最小权值。

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

using ll = long long;

class Solution {
int n, idx = 0;
ll ans = 0;
int hi = 0;
vector<int> c, dfn, low;
vector<bool> vis, flag, vis2;
unordered_set<int> meet;
vector<int> cuts;

void tarjan(int u, int p) {
vis[u] = true;
dfn[u] = low[u] = ++idx;
int child = 0;
for (int v : adj[u]) {
if (!vis[v]) {
child++;
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (p != u && low[v] >= dfn[u] && !flag[u]) {
flag[u] = true;
cuts.push_back(u);
}
} else if (v != p)
low[u] = min(low[u], dfn[v]);
}

if (p == u && child >= 2 && !flag[u]) {
flag[u] = true;
cuts.push_back(u);
}
}

int dfs(int u, int p) {
int lo = c[u];
for (int v : adj[u]) {
if (flag[v])
meet.insert(v);
if (flag[v] || vis2[v])
continue;
vis2[v] = true;
lo = min(lo, dfs(v, u));
}
if (meet.size() >= 2)
return 0;
return lo;
}

public:
ll minimumCost(vector<int>& cost, vector<vector<int>>& roads) {
this->c = cost;
n = (int)cost.size();
dfn = vector<int>(n);
low = vector<int>(n);
vis = vector<bool>(n);
flag = vector<bool>(n);
}

tarjan(0, 0);

vis2 = vector<bool>(n);
int comp = 0;
for (int i = 0; i < n; ++i)
if (!flag[i] && !vis2[i]) {
vis2[i] = true;
meet.clear();
int ret = dfs(i, i);
hi = max(hi, ret);
ans += ret;
comp++;
}

return comp == 1 ? ans : ans - hi;
}
};

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81