# # Google Kick Start 2021 Round B 题解

## # Problem A - Increasing Substring (opens new window)

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

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

using namespace std;

template <typename T>
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: 1 ", case_num);
int n;
string s;
cin >> s;
int last = 1;
for (int i = 1; i < n; i++) {
last = s[i] > s[i - 1] ? (last + 1) : 1;
printf("%d ", last);
}

printf("\n");
}
};

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
42
43

## # Problem B - Longest Progression (opens new window)

• 结合$l[i-1]$$r[i+1]$
• 结合$l[i-1]$$a[i+1]$
• 结合$a[i-1]$$r[i+1]$

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

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

using namespace std;

template <typename T>
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;
vector<int> a(n);
for (int i = 0; i < n; ++i) read(a[i]);

if (n <= 3) {
printf("%d\n", n);
return;
}

vector<int> l(n), r(n);
l[0] = 1;
l[1] = 2;
for (int i = 2; i < n; ++i) {
if (a[i] - a[i - 1] == a[i - 1] - a[i - 2])
l[i] = l[i - 1] + 1;
else
l[i] = 2;
}

r[n - 1] = 1;
r[n - 2] = 2;
for (int i = n - 3; i >= 0; --i) {
if (a[i + 1] - a[i] == a[i + 2] - a[i + 1])
r[i] = r[i + 1] + 1;
else
r[i] = 2;
}

int ans = max(l[n - 2] + 1, r[1] + 1);
for (int i = 1; i < n - 1; ++i) {
ans = max(ans, max(l[i - 1] + 1, r[i + 1] + 1));
if (i >= 2 && a[i + 1] - a[i - 1] == 2 * (a[i - 1] - a[i - 2]))
ans = max(ans, l[i - 1] + 2);
if (i + 2 < n && a[i + 1] - a[i - 1] == 2 * (a[i + 2] - a[i + 1]))
ans = max(ans, r[i + 1] + 2);
if (i >= 2 && i + 2 < n &&
a[i + 1] - a[i - 1] == 2 * (a[i - 1] - a[i - 2]) &&
a[i - 1] - a[i - 2] == a[i + 2] - a[i + 1])
ans = max(ans, l[i - 1] + r[i + 1] + 1);
}

printf("%d\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

## # Problem C - Consecutive Primes (opens new window)

### # 解法一：找出最接近$\sqrt{S}$的三个素数$A

#include <cmath>
#include <cstdio>
#include <iostream>

using namespace std;
using ll = long long;

template <typename T>
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;
}

int mod_pow(int a, int b, int mod) {
int result = 1;

while (b > 0) {
if (b & 1) result = 1LL * result * a % mod;
a = 1LL * a * a % mod;
b >>= 1;
}

return result;
}

bool miller_rabin(int n) {
if (n < 2) return false;

// Check small primes.
for (int p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29})
if (n % p == 0) return n == p;

int r = __builtin_ctz(n - 1);
int d = (n - 1) >> r;

// https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Testing_against_small_sets_of_bases
for (int a : {2, 7, 61}) {
int x = mod_pow(a % n, d, n);
if (x <= 1 || x == n - 1) continue;
for (int i = 0; i < r - 1 && x != n - 1; i++) x = 1LL * x * x % n;
if (x != n - 1) return false;
}

return true;
}

class Solution {
public:
void solve(int case_num) {
printf("Case #%d: ", case_num);
ll s;

if (s < 15) {
printf("6\n");
return;
}

int n = sqrt(s);
int b = n;
while (!miller_rabin(b)) b--;
int a = b - 1;
while (!miller_rabin(a)) a--;
int c = n + 1;
while (!miller_rabin(c)) c++;

if (1LL * b * c <= s)
printf("%lld\n", 1LL * b * c);
else
printf("%lld\n", 1LL * a * b);
}
};

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

### # 解法二：找出所有素数，然后二分查找

• 时间复杂度为$\mathcal{O}(\sqrt{\text{MAXN}}+Q\log\frac{\sqrt{\text{MAXN}}}{\ln\sqrt{\text{MAXN}}})$
• 空间复杂度为$\mathcal{O}(\sqrt{\text{MAXN}})$

#include <bitset>
#include <cstdio>
#include <iostream>
#define MAXN 1000000010
#define MAXP 51000000

using namespace std;
typedef long long ll;

bitset<MAXN> p;
int primes[MAXP], ptr = 0;

template <typename T>
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);
ll n;
int lo = 0, hi = ptr - 2;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
ll prod = 1LL * primes[mid] * primes[mid + 1];
if (prod <= n)
lo = mid + 1;
else
hi = mid - 1;
}
printf("%lld\n", 1LL * primes[lo - 1] * primes[lo]);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

p[1] = true;
for (int i = 2; i < MAXN; ++i) {
if (!p[i]) primes[ptr++] = i;
for (int j = 0; j < ptr && 1LL * i * primes[j] < MAXN; ++j) {
p[i * primes[j]] = true;
if (i % primes[j] == 0) break;
}
}

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

## # Problem D - Truck Delivery (opens new window)

• 时间复杂度为$\mathcal{O}((N+Q)\sqrt{N})$，如果块的大小设置为$\sqrt{N}$。在下面的代码中，块的大小被固定为500，这是为了避免对边的限重进行离散化。注意到$L_i$各不相同，所以每个大小为$\sqrt{N}$的块里至多有$\sqrt{N}$条边，这保证了时间复杂度的正确性。
• 空间复杂度为$\mathcal{O}(N\sqrt{N})$

#include <cstdio>
#include <iostream>
#include <vector>
#define LMAX 200000
#define LBLKSIZE 500
#define LBLKNUM 400

using namespace std;
typedef long long ll;

template <typename T>
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;
}

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

class Solution {
vector<int> limit, from, to;
vector<ll> toll;
vector<vector<ll>> acc;
vector<vector<int>> last;

void dfs(int u, int p, vector<ll> &gcd_memo, vector<int> &last_memo) {
for (auto [v, i] : adj[u]) {
if (v == p) continue;
int lidx = (limit[i] - 1) / LBLKSIZE;

// Save current value.
int last_tmp = last_memo[lidx];
ll gcd_tmp = gcd_memo[lidx];

// Modify.
last_memo[lidx] = i;
gcd_memo[lidx] = gcd(gcd_memo[lidx], toll[i]);
last[v] = vector<int>(last_memo);
acc[v] = vector<ll>(gcd_memo);
from[i] = u;
to[i] = v;

// Do recursion.
dfs(v, u, gcd_memo, last_memo);

// Restore.
last_memo[lidx] = last_tmp;
gcd_memo[lidx] = gcd_tmp;
}
}

public:
void solve(int case_num) {
printf("Case #%d: ", case_num);
int n, q;
adj = vector<vector<pair<int, int>>>(n + 1);
limit = vector<int>(n - 1);
toll = vector<ll>(n - 1);
from = vector<int>(n - 1);
to = vector<int>(n - 1);
acc = vector<vector<ll>>(n, vector<ll>(LBLKNUM));
last = vector<vector<int>>(n, vector<int>(LBLKNUM, -1));

for (int i = 0; i < n - 1; ++i) {
int x, y;
x--, y--;
}

vector<int> last_memo(LBLKNUM, -1);
vector<ll> gcd_memo(LBLKNUM);
dfs(0, -1, gcd_memo, last_memo);

while (q--) {
ll ans = 0;
int x, w;
x--;
int lidx = (w - 1) / LBLKSIZE;
for (int i = 0; i < lidx; ++i) {
ans = gcd(ans, acc[x][i]);
}
while (true) {
int r = last[x][lidx];
if (r == -1) break;
if (w >= limit[r]) ans = gcd(ans, toll[r]);
x = from[r];
}

printf("%lld ", ans);
}

printf("\n");
}
};

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
105
106
107
108
109
110
111
112
113
114