Retype
题目描述
题目链接：https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff49/000000000043adc7#problem
解题思路
这题比较简单，想要在当前关执行任何操作（进入下一层、返回上一层、退出、重开游戏）都需要花费1min的时间。
因此仅需要直接计算，重开和返回到k层取剑两种情况所需花费的总时间即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <cstdio>
using namespace std;
int cal(int n, int k, int s) {
int go_back = 2 * (k - s) + n;
int restart = n + k;
return go_back < restart? go_back : restart;
}
int main() {
int T, N, S, K;
scanf("%d", &T);
for (int i = 0; i < T; ++i) {
scanf("%d%d%d", &N, &K, &S);
printf("Case #%d: %d\n", i + 1, cal(N, K, S));
}
return 0;
}
|
Boring Numbers
题目描述
题目链接：https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff49/000000000043b0c6
解题思路
很容易发现，奇偶各有5个，也就是说对于n位数而言，区间$[1, 10 ^ {\left (n + 1 \right)} )$内满足boring number的数字有$5 ^ n$个。
然后对于前缀，如果前缀中存在不满足的数字，那么后续也就没必要继续计算了，如1334，仅需考虑$[1, 1299]$或者说$[1, 1300]$的情况。
最后对于Test Set 2的数字，没有必要进行暴力计算，利用求$[1, L - 1]$和$[1, R]$两个区间的数量来计算$[L, R]$。
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
| #include <cstdio>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
Solution() {
memo.resize(20, 1);
pre.resize(20, 0);
for (int i = 1; i < 20; ++i) {
memo[i] = memo[i - 1] * 5;
}
for (int i = 1; i < 20; ++i) {
pre[i] = pre[i - 1] + memo[i];
}
}
long long solve(long long l, long long r) {
return cal(r) - cal(l - 1);
}
private:
vector<long long> memo;
vector<long long> pre;
vector<int> a = {0, 0, 1, 1, 2 ,2 ,3 ,3 ,4, 4};
vector<int> b = {0, 1, 1, 2, 2, 3, 3, 4, 4, 5};
long long cal(long long n) {
string s = to_string(n);
int size = s.size();
long long res = pre[size - 1];
for (int i = 1; i <= size; ++i) {
int num = s[i - 1] - '0';
if (num % 2 == i % 2) {
res += memo[size - i] * a[num];
if (i == size) {
++res;
}
} else {
res += memo[size - i] * b[num];
break;
}
}
return res;
}
};
int main() {
int T;
scanf("%d", &T);
long long L, R;
Solution A;
for (int i = 1; i <= T; ++i) {
scanf("%lld%lld", &L, &R);
printf("Case #%d: %lld\n", i, A.solve(L, R));
}
return 0;
}
|
Rugby
题目描述
题目链接：https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff49/000000000043b027#problem
解题思路
首先按照移动规则，很容易得知，水平移动和垂直移动是分开计算的，因此不需要将X与Y放在一起存储。
然后先观察Y，不难论证，水平线的位置应该在中位数上。但是对于X由于需要满足相邻的点距离1，不能直接采取Y取中位数的做法。因此需要先进行$X_i - K_i$的处理，$K_i$代表$X_i$左侧的player的数量。
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
| #include <cstdio>
#include <vector>
#include <algorithm>
#include <cinttypes>
using namespace std;
int64_t SolveX (vector<int>& x_list, int N) {
int64_t total = 0;
sort(x_list.begin(), x_list.end());
for (int i = 0; i < N; ++i) {
x_list[i] -= i;
}
sort(x_list.begin(), x_list.end());
for (int i = 0; i < N; ++i) {
total += abs(x_list[i] - x_list[N / 2]);
}
return total;
}
int64_t SolveY (vector<int>& y_list, int N) {
int64_t total = 0;
sort(y_list.begin(), y_list.end());
for (int i = 0; i < N; ++i) {
total += abs(y_list[i] - y_list[N / 2]);
}
return total;
}
int main() {
int T, N, X, Y;
scanf("%d", &T);
for (int i = 1; i <= T; ++i) {
scanf("%d", &N);
vector<int> x_list(N);
vector<int> y_list(N);
for (int j = 0; j < N; ++j) {
scanf("%d%d", &X, &Y);
x_list[j] = X;
y_list[j] = Y;
}
printf("Case #%d: %" PRId64"\n", i, SolveX(x_list, N) + SolveY(y_list, N));
}
return 0;
}
|
Friend
题目描述
题目链接：https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff49/000000000043aee7
解题思路
这道题的主要难点在于构建图。如果使用名字作为点，那么边的数量会非常大。因此可以考虑使用字母作为点。如果一个人的名字为LIZZIE，那么其与名字中带“L、I、Z、E“的均存在连线。因此用字母替代的方式可行。这里图矩阵的含义就代表着graph[i][j] = 1，名字带i的与名字带j的之间存在1个名字使得他们联通。
然后在建好图之后，很明显是一个求任意两点间的最短距离的问题，那么就可以使用Floyd算法求解。
这道题有一个点需要注意：用在Floyd中标记不可达的无穷大，不能选择INT_MAX。因为该值在计算的时候会产生溢出，就会导致在更新最短距离时，INT_MAX溢出为负的值会成为最小值。
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
| #include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#define INF 0x3f3f3f3f
using namespace std;
class Solution {
public:
Solution(int N) {
graph.resize(26, vector<int>(26, INF));
names.resize(N + 1);
string s;
for (int i = 1; i <= N; ++i) {
cin >> s;
names[i] = s;
for (int j = 0; j < s.size(); ++j) {
for (int k = j + 1; k < s.size(); ++k) {
if (s[j] != s[k]) {
graph[s[j] - 'A'][s[k] - 'A'] = 1;
graph[s[k] - 'A'][s[j] - 'A'] = 1;
}
}
}
}
floyd();
}
int solve(int x, int y) {
int min_dist = INF;
for (char cx : names[x]) {
for (char cy : names[y]) {
if (cx == cy) {
return 2;
}
min_dist = min(min_dist, graph[cx - 'A'][cy - 'A'] + 2);
}
}
return min_dist == INF? -1 : min_dist;
}
private:
int n;
vector<vector<int>> graph;
vector<string> names;
void floyd() {
for (int k = 0; k < 26; k++) {
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
}
};
int main() {
int T, N, Q, P1, P2;
scanf("%d", &T);
for (int i = 1; i <= T; ++i) {
scanf("%d%d", &N, &Q);
getchar();
Solution A(N);
printf("Case #%d:", i);
for (int j = 0; j < Q; ++j) {
scanf("%d%d", &P1, &P2);
printf(" %d", A.solve(P1, P2));
}
printf("\n");
}
return 0;
}
|