# # Leetcode 第81场双周赛题解

## # Problem A - 统计星号 (opens new window)

### # 方法一：模拟

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

class Solution {
public:
int countAsterisks(string s) {
int ans = 0, seg = 0;
for (char c : s) {
if (c == '|')
seg++;
else if (c == '*' && seg % 2 == 0)
ans++;
}
return ans;
}
};

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

## # Problem B - 统计无向图中无法互相到达点对数 (opens new window)

### # 方法一：统计连通块

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

class Solution {
public:
long long countPairs(int n, vector<vector<int>>& edges) {
long long ans = 1LL * n * (n - 1) / 2;
for (auto &e : edges) {
int u = e[0], v = e[1];
}

vector<bool> vis(n);

for (int i = 0; i < n; ++i) {
if (vis[i]) continue;

vis[i] = true;
queue<int> q;
q.push(i);
int sz = 1;

while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (!vis[v]) {
vis[v] = true;
q.push(v);
sz++;
}
}
}

ans -= 1LL * sz * (sz - 1) / 2;
}

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

## # Problem C - 操作后的最大异或和 (opens new window)

### # 方法一：脑筋急转弯

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

class Solution {
public:
int maximumXOR(vector<int>& nums) {
int ans = 0;
for (int num : nums)
ans |= num;
return ans;
}
};

1
2
3
4
5
6
7
8
9

## # Problem D - 不同骰子序列的数目 (opens new window)

### # 方法一：动态规划

• 时间复杂度 $\mathcal{O}(N\cdot C^3)$，其中 $C=6$
• 空间复杂度 $\mathcal{O}(N)$

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

ll dp[7][7]{}, ndp[7][7]{};
int g[7][7];

class Solution {
public:
int distinctSequences(int n) {
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;

for (int i = 1; i <= 6; ++i)
for (int j = 1; j <= 6; ++j)
g[i][j] = __gcd(i, j);

for (int i = 0; i < n; ++i) {
memset(ndp, 0, sizeof(ndp));

for (int a = 0; a <= 6; ++a) {
for (int b = 0; b <= 6; ++b) {
if (dp[a][b] == 0)
continue;

for (int c = 1; c <= 6; ++c) {
if (c == a || c == b || (b != 0 && g[b][c] != 1))
continue;

ndp[b][c] += dp[a][b];
ndp[b][c] %= MOD;
}
}
}

swap(dp, ndp);
}

ll ans = 0;

for (int a = 0; a <= 6; ++a) {
for (int b = 0; b <= 6; ++b) {
ans += dp[a][b];
ans %= MOD;
}
}

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