# # Leetcode 第60场双周赛题解

## # Problem A - 找到数组的中间位置 (opens new window)

### # 方法一：模拟

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

class Solution:
def findMiddleIndex(self, nums: List[int]) -> int:
right = sum(nums)
left = 0
for i in range(len(nums)):
right -= nums[i]
if left == right:
return i
left += nums[i]
return -1

1
2
3
4
5
6
7
8
9
10

## # Problem B - 找到所有的农场组 (opens new window)

### # 方法一：贪心

• 时间复杂度为$\mathcal{O}(RC)$
• 空间复杂度$\mathcal{O}(RC)$

class Solution {
public:
vector<vector<int>> findFarmland(vector<vector<int>>& land) {
int n = land.size(), m = land[0].size();
auto good = [&](int i, int j) {
if (land[i][j] == 0)
return false;
if (i > 0 && land[i - 1][j] == 1)
return false;
if (j > 0 && land[i][j - 1] == 1)
return false;
return true;
};
vector<vector<int>> ans;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) {
if (good(i, j)) {
int r = j;
while (r + 1 < m && land[i][r + 1] == 1)
r++;
int d = i;
while (d + 1 < n && land[d + 1][j] == 1)
d++;
ans.push_back({i, j, d, r});
}
}
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

## # Problem C - 树上的操作 (opens new window)

### # 方法一：模拟

lockunlock比较简单，upgrade需要三步：

1. 逐层上跳，检查祖先中是否有锁。
2. DFS检查子树中是否有锁。
3. DFS清除子树中的锁。
• 预处理时间复杂度$\mathcal{O}(N)$lockunlock时间复杂度$\mathcal{O}(1)$upgrade时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(N)$

class LockingTree {
int n;
vector<int> parent, locked;

bool has_lock(int u) {
if (locked[u])
return true;

if (has_lock(v))
return true;

return false;
}

void batch_unlock(int u) {
locked[u] = 0;
batch_unlock(v);
}

public:
LockingTree(vector<int>& parent) {
this->parent = parent;
n = parent.size();
locked = vector<int>(n);
for (int i = 1; i < n; ++i)
}

bool lock(int num, int user) {
if (!locked[num]) {
locked[num] = user;
return true;
}
return false;
}

bool unlock(int num, int user) {
if (locked[num] == user) {
locked[num] = 0;
return true;
}
return false;
}

bool upgrade(int num, int user) {
int p = num;
while (p != -1) {
if (locked[p])
return false;
p = parent[p];
}

if (!has_lock(num))
return false;

batch_unlock(num);
locked[num] = user;
return true;
}
};

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

## # Problem D - 好子集的数目 (opens new window)

### # 方法一：动态规划预处理+枚举

1. 子集的乘积大于$1$，也即必须有非$1$的元素。
2. 子集中任意一个质因子最多出现一次。

• 质数：[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
• 两个不同质数的乘积：[6, 10, 14, 22, 26, 15, 21]
• 三个不同质数的乘积：[30]

• 预处理时间复杂度$\mathcal{O}(M\cdot2^M+N)$，每次运行时间复杂度$\mathcal{O}(M\cdot K+N)$，其中$M=18$$K=3327$
• 空间复杂度$\mathcal{O}(2^M+MAXN)$

const int MOD = 1e9 + 7;
const int p[18] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 6, 10, 14, 22, 26, 15, 21, 30};
bool inited = false;
int two[100001];
bool g[18][18]{}, good[1 << 18]{};
vector<int> good_subset;

int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x % y);
}

void init() {
inited = true;

for (int i = 0; i < 18; ++i)
for (int j = i + 1; j < 18; ++j) {
if (gcd(p[i], p[j]) == 1)
g[i][j] = true;
}

good[0] = true;
for (int i = 1; i < (1 << 18); ++i) {
for (int j = 0; j < 18; ++j) {
if (i & (1 << j)) {
bool valid = good[i ^ (1 << j)];
if (valid) {
for (int k = j + 1; k < 18; ++k) {
if ((i & (1 << k)) && !g[j][k]) {
valid = false;
break;
}
}
}
good[i] = valid;
break;
}
}

if (good[i])
good_subset.emplace_back(i);
}

two[0] = 1;
for (int i = 1; i <= 100000; ++i)
two[i] = two[i - 1] * 2 % MOD;
}

class Solution {
public:
int numberOfGoodSubsets(vector<int>& nums) {
if (!inited)
init();

int n = nums.size();
vector<int> cnt(31);
for (int num : nums)
cnt[num]++;

int ans = 0;
for (int i : good_subset) {
int curr = 1;
for (int j = 0; j < 18 && curr; ++j)
if (i & (1 << j))
curr = 1LL * curr * cnt[p[j]] % MOD;
ans = (ans + curr) % MOD;
}

return 1LL * ans * two[cnt[1]] % MOD;
}
};

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