﻿ Google kickstart 2022 Round A题解 - 鸿网互联

# Google kickstart 2022 Round A题解

Speed Typing题意概述 给出两个字符串 I 和 P ，问能否通过删除 P 中若干个字符得到 I ？如果能的话，需要删除字符的个数是多少？ 数据规模 $1≤|I|,|P|≤10^5$ 双指针 设置两个指针 i 和
Speed Typing 题意概述

$1≤|I|,|P|≤10^5$

• 时间复杂度为$$O(max(|I|,|P|))$$
• 空间复杂度为$$O(1)$$
C++代码
#include <bits/stdc++.h>
using namespace std;
using gg = long long;
#define rep(i, a, b, c) for (gg i = (a); i <= (b); i += (c))
#define rrep(i, a, b, c) for (gg i = (a); i >= (b); i -= (c))
constexpr gg MAX = 1e6 + 5;
constexpr gg mod = 1e9 + 7;
constexpr gg INF = 4e18;
constexpr double eps = 1e-12;
gg ti, ni, mi, ki, di, pi, xi, yi;
gg up(gg n, gg m) { return n >= 0 ? (n + m - 1) / m : n / m; }
gg down(gg n, gg m) { return n >= 0 ? n / m : (n - m + 1) / m; }
//! ti; MAX; mod; 边界
void solve() {
string s1, s2;
cin >> s1 >> s2;
gg i = 0, j = 0;
for (; i < s1.size() and j < s2.size(); ++i, ++j) {
while (j < s2.size() and s1[i] != s2[j]) {
++j;
}
if (j == s2.size()) {
break;
}
}
i == s1.size() ? cout << s2.size() - s1.size() : cout << "IMPOSSIBLE";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ti = 1;
cin >> ti;
for (gg ii = 1; ii <= ti; ++ii) {
cout << "Case #" << ii << ": ";
solve();
cout << "\n";
}
return 0;
}

Challenge Nine 题意概述

$1≤N≤10^{123456}$

• 时间复杂度为$$O(n)$$
• 空间复杂度为$$O(n)$$

C++代码
#include <bits/stdc++.h>
using namespace std;
using gg = long long;
#define rep(i, a, b, c) for (gg i = (a); i <= (b); i += (c))
#define rrep(i, a, b, c) for (gg i = (a); i >= (b); i -= (c))
constexpr gg MAX = 1e6 + 5;
constexpr gg mod = 1e9 + 7;
constexpr gg INF = 4e18;
constexpr double eps = 1e-12;
gg ti, ni, mi, ki, di, pi, xi, yi;
gg up(gg n, gg m) { return n >= 0 ? (n + m - 1) / m : n / m; }
gg down(gg n, gg m) { return n >= 0 ? n / m : (n - m + 1) / m; }
//! ti; MAX; mod; 边界
void solve() {
string n;
cin >> n;
gg m = n.size(), sum = 0;
array<gg, 2> ans{m + 1, 10};
for (char c : n) {
sum += c - '0';
}
n.push_back(10 + '0');
rep(i, 0, 9, 1) {
if ((i + sum) % 9 == 0) {
rep(j, 0, m, 1) {
if (n[j] - '0' > i and (j > 0 or i != 0) and ans[0] > j) {
ans = {j, i};
break;
}
}
}
}
n.pop_back();
cout << n.substr(0, ans[0]) << ans[1] << n.substr(ans[0]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ti = 1;
cin >> ti;
for (gg ii = 1; ii <= ti; ++ii) {
cout << "Case #" << ii << ": ";
solve();
cout << "\n";
}
return 0;
}

Palindrome Free Strings 题意概述

$1<=N<=5\times 10^4$

$$dp[i]$$表示以S的前i个字符能否找到一种替换方法保证没有长度大于等于5的回文子串。由于要验证是否包含长度为6的回文子串，那么在每次添加新的字符S[i]时，S[i]能否构成长度为6的回文子串与S[i]前面的5个字符S[i-5],S[i-4],S[i-3],S[i-2],S[i-1]有关，因此，可以为S[i]的前5个字符标记一个状态，由于每个字符的取值只有01两种，因此状态总数为$$2^5$$。针对字符S[i]，暴力枚举以S[i]结尾的长度为6的子串的可能替换结果字符串j，如果j包含长度为5或6的回文子串，则不符合题目要求；否则$$dp[i][j]=dp[i-1][j']$$，其中$$j'=S[i-6]+j[:5]$$。具体实现可参考代码。

• 时间复杂度为$$O(2^K\cdot N)$$
• 空间复杂度为$$O(2^K\cdot N)$$

C++代码
#include <bits/stdc++.h>
using namespace std;
using gg = long long;
#define rep(i, a, b, c) for (gg i = (a); i <= (b); i += (c))
#define rrep(i, a, b, c) for (gg i = (a); i >= (b); i -= (c))
constexpr gg MAX = 1e5 + 5;
constexpr gg MAX2 = 70;
constexpr gg mod = 1e9 + 7;
constexpr gg INF = 4e18;
constexpr double eps = 1e-12;
gg ti, ni, mi, ki, di, pi, xi, yi;
gg up(gg n, gg m) { return n >= 0 ? (n + m - 1) / m : n / m; }
gg down(gg n, gg m) { return n >= 0 ? n / m : (n - m + 1) / m; }
//! ti; MAX; mod; 边界
bool dp[MAX][MAX2];
string s;
void dfs(gg p, gg r, string cur, vector<string>& v) {
if (p > r) {
v.push_back(cur);
return;
}
if (s[p] != '1') {
dfs(p + 1, r, cur + "0", v);
}
if (s[p] != '0') {
dfs(p + 1, r, cur + "1", v);
}
}
bool isPalic(const string& s) { return equal(s.begin(), s.end(), s.rbegin()); }
void solve() {
cin >> ni >> s;
if (ni <= 4) {
cout << "POSSIBLE";
} else if (ni == 5) {
vector<string> v;
dfs(0, 4, "", v);
bool ans = all_of(v.begin(), v.end(), isPalic);
cout << (ans ? "IMPOSSIBLE" : "POSSIBLE");
} else {
bool ans = false;
rep(i, 5, ni - 1, 1) {
vector<string> v;
dfs(i - 5, i, "", v);
for (string& k : v) {
gg cur = stoll(k, 0, 2);
dp[i][cur] = not(isPalic(k) or isPalic(k.substr(0, 5)) or isPalic(k.substr(1, 5)));
if (i >= 6) {
bool res = false;
if (s[i - 6] != '1') {
res = res or dp[i - 1][stoll("0" + k.substr(0, 5), 0, 2)];
}
if (s[i - 6] != '0') {
res = res or dp[i - 1][stoll("1" + k.substr(0, 5), 0, 2)];
}
dp[i][cur] = dp[i][cur] and res;
}
if (i == ni - 1) {
ans = ans or dp[i][cur];
}
}
}
cout << (ans ? "POSSIBLE" : "IMPOSSIBLE");
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ti = 1;
cin >> ti;
for (gg ii = 1; ii <= ti; ++ii) {
cout << "Case #" << ii << ": ";
solve();
cout << "\n";
}
return 0;
}

Interesting Integers 题意概述

$1≤A≤B≤10^5（小数据）$

• 时间复杂度为$$O(n)$$
• 空间复杂度为$$O(n)$$

C++代码
#include <bits/stdc++.h>
using namespace std;
using gg = long long;
#define rep(i, a, b, c) for (gg i = (a); i <= (b); i += (c))
#define rrep(i, a, b, c) for (gg i = (a); i >= (b); i -= (c))
constexpr gg MAX = 1e5 + 5;
constexpr gg MAX2 = 70;
constexpr gg mod = 1e9 + 7;
constexpr gg INF = 4e18;
constexpr double eps = 1e-12;
gg ti, ni, mi, ki, di, pi, xi, yi;
gg up(gg n, gg m) { return n >= 0 ? (n + m - 1) / m : n / m; }
gg down(gg n, gg m) { return n >= 0 ? n / m : (n - m + 1) / m; }
//! ti; MAX; mod; 边界
bool func(gg n) {
gg s = 0, p = 1;
while (n > 0) {
s += n % 10;
p *= n % 10;
n /= 10;
}
return p % s == 0;
}
void solve() {
cin >> xi >> yi;
gg ans = 0;
rep(i, xi, yi, 1) {
if (func(i)) {
++ans;
}
}
cout << ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ti = 1;
cin >> ti;
for (gg ii = 1; ii <= ti; ++ii) {
cout << "Case #" << ii << ": ";
solve();
cout << "\n";
}
return 0;
}


<