# Google Kick Start 2022 Round A 题解

# Problem A - Speed Typing (opens new window)

# 方法一：单指针

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

#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);

string s, f;
cin >> f >> s;

int ptr = 0;
for (char ch : s) {
if (ptr < f.size() && ch == f[ptr]) ptr++;
}

if (ptr == f.size())
printf("%d\n", (int)s.size() - (int)f.size());
else
printf("IMPOSSIBLE\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
44
45

# Problem B - Challenge Nine (opens new window)

# 方法一：数学+贪心

• 时间复杂度为$\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);

string N;
cin >> N;
int sum = 0;
for (char ch : N) sum += ch - '0';
int need = (9 - sum % 9) % 9;
if (need == 0) {
cout << N[0] << '0' << N.substr(1) << endl;
return;
}
int n = N.size();
for (int i = 0; i < n; ++i) {
if (N[i] > (need + '0')) {
cout << N.substr(0, i) << (char)(need + '0') << N.substr(i, n - i)
<< endl;
return;
}
}
cout << N << (char)(need + '0') << endl;
}
};

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
44
45
46
47
48
49
50
51

# Problem C - Palindrome Free Strings (opens new window)

# 方法一：动态规划

• 时间复杂度为$\mathcal{O}(2^K\cdot|S|)$，其中 $K=5$
• 空间复杂度为$\mathcal{O}(2^K)$

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

using namespace std;
const int K = 5;
const int MSK1 = (1 << K) - 1;
const int MSK = (1 << (K + 1)) - 1;

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;
}

bool bad[1 << (K + 1)]{};

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

int n;
string s;
cin >> n >> s;

if (n <= 4) {
cout << "POSSIBLE" << endl;
return;
}

vector<bool> dp(1 << (K + 1));
dp[0] = true;
for (int i = 0; i < n; ++i) {
vector<bool> ndp(1 << (K + 1));
if (s[i] == '0' || s[i] == '?') {
for (int j = 0; j <= MSK; ++j) {
if (!dp[j]) continue;
int nxt1 = (j << 1) & MSK1;
if (i >= 4 && bad1[nxt1]) continue;
int nxt = (j << 1) & MSK;
if (i >= 5 && bad[nxt]) continue;
ndp[nxt] = true;
}
}
if (s[i] == '1' || s[i] == '?') {
for (int j = 0; j <= MSK; ++j) {
if (!dp[j]) continue;
int nxt1 = ((j << 1) & MSK1) + 1;
if (i >= 4 && bad1[nxt1]) continue;
int nxt = ((j << 1) & MSK) + 1;
if (i >= 5 && bad[nxt]) continue;
ndp[nxt] = true;
}
}
dp = move(ndp);
}

for (int i = 0; i < MSK; ++i) {
if (dp[i]) {
cout << "POSSIBLE" << endl;
return;
}
}

cout << "IMPOSSIBLE" << endl;
}
};

bool is_palindrom(string s) {
string t(s.rbegin(), s.rend());
return s == t;
}

int main() {
for (int i = 0; i < (1 << K); i++) {
string s = bitset<K>(i).to_string();
}

for (int i = 0; i < (1 << (K + 1)); i++) {
string s = bitset<K + 1>(i).to_string();
}

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

# Problem D - Interesting Integers (opens new window)

# 方法一：数位动态规划

• 我们需要考察数位积与数位和的关系。在数位和一定的情况下，我们只需要记录当前数位积与数位和的最大公约数即可。
• 我们得到的数不能超过 $x$，这种有上限/下限的问题，可以用一个标志位来记录当前前缀是否与上限/下限相等，并分别处理。
• 前缀的零不参与乘积。所以我们还需要一个标志位来记录当前数是否已经大于零。

• $p$ 表示当前数位积与目标数位和 $sum$ 的最大公约数
• $s$ 表示当前数位和
• $z$ 为当前是否大于零的标志位
• $same$ 为当前前缀是否与上限相等的标志位

• 时间复杂度为$\mathcal{O}(S^{5/2}\cdot ND)$，其中 $S\le9\times12=108$$N$ 为上限的位数，$D=10$
• 空间复杂度为$\mathcal{O}(S^2)$

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

using namespace std;
using ll = long long;

int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}

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_[1200][120];
ll dp[120][120][2][2];

class Solution {
ll calc(ll num) {
if (num == 0) return 0;

string S = to_string(num);
int n = S.size();
int max_sum = 9 * n;

ll ans = 0;
for (int sum = 1; sum <= max_sum; ++sum) {
memset(dp, 0, sizeof(dp));
dp[0][0][0][1] = 1;
for (int i = 0; i < n; ++i) {
int si = S[i] - '0';
for (int p = sum; p >= 0; --p) {
// Optimization 1: p can only be 0 or a factor of sum
if (p != 0 && sum % p != 0) continue;
for (int s = min(sum, i * 9); s >= 0; --s) {
ll v00 = dp[p][s][0][0], v01 = dp[p][s][0][1], v10 = dp[p][s][1][0],
v11 = dp[p][s][1][1];
// Optimization 2: all are 0 so have no future effects
if (v00 + v01 + v10 + v11 == 0) continue;
dp[p][s][0][0] = dp[p][s][0][1] = dp[p][s][1][0] = dp[p][s][1][1] =
0;

// Enumerate choice of the current position
for (int nxt = 0; nxt <= 9; ++nxt) {
int np = gcd_[max(p, 1) * nxt][sum];
int ns = s + nxt;

// Case 1: z == 0 && same == 0
if (nxt == 0)
dp[p][s][0][0] += v00;
else if (s + nxt <= sum)
dp[np][ns][1][0] += v00;

// Case 2: z == 0 && same == 1
if (nxt == 0) {
dp[p][s][0][0] += v01;
} else {
if (nxt < si && ns <= sum) {
dp[np][ns][1][0] += v01;
} else if (nxt == si && ns <= sum) {
dp[np][ns][1][1] += v01;
}
}

// Case 3: z == 1 && same == 0
if (ns <= sum) dp[np][ns][1][0] += v10;

// Case 4: z == 1 && same == 1
if (nxt < si && ns <= sum) {
dp[np][ns][1][0] += v11;
} else if (nxt == si && ns <= sum) {
dp[np][ns][1][1] += v11;
}
}
}
}
}
ans += dp[sum][sum][1][0] + dp[sum][sum][1][1];
}

return ans;
}

public:
void solve(int case_num) {
printf("Case #%d: ", case_num);
ll A, B;
cout << calc(B) - calc(A - 1) << endl;
}
};

int main() {
int t;

// Optimization 3: Precalculate GCDs
for (int i = 0; i < 1200; ++i)
for (int j = 0; j < 120; ++j) gcd_[i][j] = gcd(i, j);

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
115