# Google Kick Start 2020 Round H 题解
# Problem A - Retype (opens new window)
一共只有两种选择,我们直接计算出来对应的耗时,取较小的那个即可。
时间复杂度为。
参考代码(C++)
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
void solve(int case_num) {
cout << "Case #" << case_num << ": ";
long long N, K, S;
cin >> N >> K >> S;
cout << K - 1 + min(N + 1, K - S + N - S + 1) << endl;
}
};
int main() {
int t;
cin >> t;
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Problem B - Boring Numbers (opens new window)
所有类似这样求范围内符合条件的数的个数的题目,都可以变为分别求范围和范围内的个数,然后二者相减即可得到答案。
如何求范围内符合条件的数的个数呢?
首先,我们考虑所有位数比小的数。对于一个位数,Boring Number的总个数显然为(每一位有个数字可以选择)。所以说,如果有位,那么所有位数比小的数的贡献为。
接下来,我们考虑所有小于等于的位数。
我们从最高位开始。假设当前处理到第位。
- 如果在当前位置的数字不符合条件(奇偶性),那么我们只要统计出所有比小的数字中符合条件的数的个数(预设为),然后给总数加上即可。因为对于这个数,后面的位是可以任意选择的。在这种情况下,我们不需要继续向后处理了。
- 否则,我们首先统计出比小的数字中符合条件的数的个数(预设为),给总数加上。接下来,我们还需要考虑第位取为的符合条件的数的个数,继续向后进行即可。需要注意的是,如果,我们直接在总数上加上,表示自己就是一个符合条件的数。
时间复杂度为(这里没有考虑预处理的时间)。
参考代码(C++)
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
ll five[20], pre[20];
int a[10] = {0, 0, 1, 1, 2, 2, 3, 3, 4, 4};
int b[10] = {0, 1, 1, 2, 2, 3, 3, 4, 4, 5};
class Solution {
ll count(ll x) {
string s = to_string(x);
int n = s.size();
ll ans = pre[n - 1];
for (int i = 1; i <= n; ++i) {
int c = s[i - 1] - '0';
if (c % 2 != i % 2) {
ans += five[n - i] * b[c];
break;
} else {
ans += five[n - i] * a[c];
if (i == n)
ans++;
}
}
return ans;
}
public:
void solve(int case_num) {
cout << "Case #" << case_num << ": ";
ll L, R;
cin >> L >> R;
cout << count(R) - count(L - 1) << endl;
}
};
int main() {
int t;
cin >> t;
five[0] = 1;
for (int i = 1; i < 20; ++i)
five[i] = five[i - 1] * 5;
pre[0] = 0;
for (int i = 1; i < 20; ++i)
pre[i] = pre[i - 1] + five[i];
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}
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
# Problem C - Rugby (opens new window)
显然,方向和方向的移动步数是相互独立的。
首先考虑方向。因为最后所有数的是一样的,所以这就变成了一道经典问题,直接取的中位数即可。
接下来考虑方向。显然,在起点确定之后,我们的移动方案也就随之确定——所有人按照排序,然后从左到右依次去对应的格子即可。
接下来,我们可以用三分查找的方法求出最后的答案。为了说明三分查找的正确性,我们需要说明距离函数只有一个极小值,同时这个极小值也是最小值(如果考虑整点,则可能有两个,但这两个点必然是相邻的两个整数)。
显然,当时,随着的增大,总是减小的;而当时,随着的增大,总是增大的。
我们发现,当在某一位置时,将起点从移动到,有个人的移动距离会减小,同时有个人的移动距离会增加,因此。在从移动到的过程中,从减小到,并且整个过程中不会增大。所以说,将会从增加到,并且过程中不会减小。因此,总会在满足的最小的处取得极小值,同时也是最小值。
最后的时间复杂度为,这里的为我们进行三分查找的范围。
参考代码(C++,三分查找)
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
class Solution {
public:
void solve(int case_num) {
cout << "Case #" << case_num << ": ";
int N;
cin >> N;
vector<int> X(N), Y(N);
for (int i = 0; i < N; ++i)
cin >> X[i] >> Y[i];
sort(Y.begin(), Y.end());
ll ylo = 0;
for (int yi : Y)
ylo += abs(yi - Y[N / 2]);
sort(X.begin(), X.end());
ll l = -2e9, r = 2e9;
ll xlo = LLONG_MAX;
auto dist = [&](ll start) {
ll ret = 0;
int idx = 0;
for (int xi : X) {
ret += abs(start + idx - xi);
idx++;
}
xlo = min(xlo, ret);
return ret;
};
while (l <= r) {
ll ml = l + (r - l) / 3, mr = r - (r - l) / 3;
ll dl = dist(ml), dr = dist(mr);
if (dl <= dr)
r = mr - 1;
if (dl >= dr)
l = ml + 1;
}
cout << ylo + xlo << endl;
}
};
int main() {
int t;
cin >> t;
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}
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
我们也可以对或进行二分查找,方法是类似的。
Code (C++,二分查找)
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
class Solution {
public:
void solve(int case_num) {
cout << "Case #" << case_num << ": ";
int N;
cin >> N;
vector<int> X(N), Y(N);
for (int i = 0; i < N; ++i)
cin >> X[i] >> Y[i];
sort(Y.begin(), Y.end());
ll ylo = 0;
for (int yi : Y)
ylo += abs(yi - Y[N / 2]);
sort(X.begin(), X.end());
ll l = -2e9, r = 2e9;
ll xlo = LLONG_MAX;
auto dist = [&](ll start) {
ll ret = 0;
int idx = 0;
for (int xi : X) {
ret += abs(start + idx - xi);
idx++;
}
xlo = min(xlo, ret);
return ret;
};
while (l <= r) {
ll mid = (l + r) / 2;
ll delta = dist(mid + 1) - dist(mid);
if (delta >= 0)
r = mid - 1;
else
l = mid + 1;
}
cout << ylo + xlo << endl;
}
};
int main() {
int t;
cin >> t;
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}
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
事实上,我们也可以对使用中位数方法。但是,我们需要在第一次排序后,用替换,然后再次排序。官方题解 (opens new window)给出了很好的解释。
Code (C++,对$x$两次排序)
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
class Solution {
public:
void solve(int case_num) {
cout << "Case #" << case_num << ": ";
int N;
cin >> N;
vector<int> X(N), Y(N);
for (int i = 0; i < N; ++i)
cin >> X[i] >> Y[i];
sort(Y.begin(), Y.end());
ll ylo = 0;
for (int yi : Y)
ylo += abs(yi - Y[N / 2]);
sort(X.begin(), X.end());
for (int i = 0; i < N; ++i)
X[i] -= i;
sort(X.begin(), X.end());
ll xlo = 0;
for (int xi : X)
xlo += abs(xi - X[N / 2]);
cout << ylo + xlo << endl;
}
};
int main() {
int t;
cin >> t;
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}
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
# Problem D - Friends (opens new window)
因为最多有个不同的字符串,所以如果我们以字符串为节点建图,边数的规模会非常大。
转变思路,我们考虑以字母为节点来建图,并用邻接矩阵来表示这个图。初始状态为,。如果两个不同的字母和同时出现在了一个字符串中,我们就设置。这里的含义是,如果我们现在有一个含有的字符串和另一个含有的字符串,那么可以通过构建一个链,这个链的中间节点有个。
接下来,我们在这个邻接矩阵上跑一遍Floyd算法,从而现在就表示到的链的最少的中间节点数。
最后,对于每一个查询,我们遍历的字母和的字母的配对,则最后的答案为
如果结果为,则说明无解。
总时间复杂度为,其中为字母表的大小。
参考代码(C++)
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
class Solution {
public:
void solve(int case_num) {
cout << "Case #" << case_num << ": ";
int N, Q;
cin >> N >> Q;
vector<string> S(N + 1);
for (int i = 1; i <= N; ++i)
cin >> S[i];
vector<vector<int>> d(26, vector<int>(26, INF));
for (string s : S)
for (char c1 : s)
for (char c2 : s)
if (c1 != c2)
d[c1 - 'A'][c2 - 'A'] = 1;
for (int k = 0; k < 26; ++k)
for (int i = 0; i < 26; ++i) {
if (i == k)
continue;
for (int j = 0; j < 26; ++j) {
if (j == i || j == k)
continue;
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
for (int i = 1; i <= Q; ++i) {
int X, Y;
cin >> X >> Y;
int ans = INF;
bool found = false;
for (char c1 : S[X]) {
for (char c2 : S[Y]) {
if (c1 == c2) {
cout << 2 << " ";
found = true;
break;
}
ans = min(ans, d[c1 - 'A'][c2 - 'A'] + 2);
}
if (found)
break;
}
if (!found)
cout << (ans == INF ? -1 : ans) << " ";
}
cout << endl;
}
};
int main() {
int t;
cin >> t;
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}
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