# # Google Kick Start 2021 Round A 题解

## # Problem A - K-Goodness String (opens new window)

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

#include <cstdio>
#include <iostream>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve(int case_num) {
printf("Case #%d: ", case_num);
int n, k;
string s;
cin >> s;
int cnt = 0;
for (int i = 0; i < n / 2; ++i) {
if (s[i] != s[n - 1 - i])
cnt++;
}
printf("%d\n", abs(cnt - k));
}
};

int main() {
int t;
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}
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

## # Problem B - L Shaped Plots (opens new window)

• WN
• WS
• EN
• ES

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

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve(int case_num) {
printf("Case #%d: ", case_num);
int r, c;
vector<vector<int>> m(r, vector<int>(c));
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
vector<vector<int>> W(r, vector<int>(c));
vector<vector<int>> E(r, vector<int>(c));
vector<vector<int>> N(r, vector<int>(c));
vector<vector<int>> S(r, vector<int>(c));
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
if (m[i][j]) {
W[i][j] = 1;
if (j >= 1)
W[i][j] += W[i][j - 1];
}
}
for (int j = c - 1; j >= 0; --j) {
if (m[i][j]) {
E[i][j] = 1;
if (j + 1 < c)
E[i][j] += E[i][j + 1];
}
}
}
for (int j = 0; j < c; ++j) {
for (int i = 0; i < r; ++i) {
if (m[i][j]) {
N[i][j] = 1;
if (i >= 1)
N[i][j] += N[i - 1][j];
}
}
for (int i = r - 1; i >= 0; --i) {
if (m[i][j]) {
S[i][j] = 1;
if (i + 1 < r)
S[i][j] += S[i + 1][j];
}
}
}

ll ans = 0;
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j) {
ans += max(0, min(W[i][j], N[i][j] / 2) - 1);
ans += max(0, min(W[i][j] / 2, N[i][j]) - 1);
ans += max(0, min(W[i][j], S[i][j] / 2) - 1);
ans += max(0, min(W[i][j] / 2, S[i][j]) - 1);
ans += max(0, min(E[i][j], N[i][j] / 2) - 1);
ans += max(0, min(E[i][j] / 2, N[i][j]) - 1);
ans += max(0, min(E[i][j], S[i][j] / 2) - 1);
ans += max(0, min(E[i][j] / 2, S[i][j]) - 1);
}

printf("%lld\n", ans);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}

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

## # Problem C - Rabbit House (opens new window)

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

#include <cstdio>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>

using namespace std;
using ll = long long;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

const int d[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

class Solution {
public:
void solve(int case_num) {
printf("Case #%d: ", case_num);
int r, c;
vector<vector<int>> g(r, vector<int>(c));
priority_queue<tuple<int, int, int>> pq;
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j) {
pq.emplace(g[i][j], i, j);
}
vector<vector<int>> g0(g);
while (!pq.empty()) {
auto [h, i, j] = pq.top();
pq.pop();
if (h < g[i][j])
continue;
for (int k = 0; k < 4; ++k) {
int ni = i + d[k][0], nj = j + d[k][1];
if (ni < 0 || ni >= r || nj < 0 || nj >= c)
continue;
if (h - 1 > g[ni][nj]) {
pq.emplace(h - 1, ni, nj);
g[ni][nj] = h - 1;
}
}
}

ll ans = 0;
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
ans += g[i][j] - g0[i][j];

printf("%lld\n", ans);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}
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

## # Problem D - Checksum (opens new window)

• 如果少于$(N-1)^2$，那么至少有$2N$个未解开的，而我们至多进行$2N-1$次推导。
• 如果多于$(N-1)^2$，则至少有一行/一列解开了$N$个格子，这显然是不必要的。

• 时间复杂度为$\mathcal{O}(N^2\log N)$（Kruskal），或$\mathcal{O}(N^2)$（Prim），因为是稠密图，所以这里用Prim算法可以有更优的时间复杂度。
• 空间复杂度为$\mathcal{O}(N^2)$.

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class UnionFind {
int n;
vector<int> parent, size;

public:
UnionFind(int n) {
this->n = n;
parent = vector<int>(n);
size = vector<int>(n, 1);
for (int i = 0; i < n; ++i)
parent[i] = i;
}

int find(int idx) {
if (parent[idx] == idx)
return idx;
return parent[idx] = find(parent[idx]);
}

void connect(int a, int b) {
int fa = find(a), fb = find(b);
if (fa != fb) {
if (size[fa] > size[fb]) {
parent[fb] = fa;
size[fa] += size[fb];
} else {
parent[fa] = fb;
size[fb] += size[fa];
}
}
}
};

class Solution {
public:
void solve(int case_num) {
printf("Case #%d: ", case_num);
int n;
vector<vector<int>> a(n, vector<int>(n));
vector<vector<int>> b(n, vector<int>(n));
vector<int> r(n);
vector<int> c(n);
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)

vector<tuple<int, int, int>> edges;
ll tot = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
tot += b[i][j];
edges.emplace_back(b[i][j], i, n + j);
}
sort(edges.rbegin(), edges.rend());
UnionFind uf(n * 2);

for (int i = 0; i < n; ++i)
for (int i = 0; i < n; ++i)

ll remove = 0;
for (auto [weight, u, v] : edges) {
if (uf.find(u) == uf.find(v))
continue;
remove += weight;
uf.connect(u, v);
}

printf("%lld\n", tot - remove);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}
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