【题解】Google Kick Start

老年人做点笔试题算了。

注:一切以 Hard 模式为准。

2019

Round F

Flattening

\(f[i][k]\) 表示前 \(i\) 个数中相邻不同的数量不超过 \(k\) 的最少操作数,有转移式 \(f[i][k] = \min_{j<i} f[j][k -1]+m(j+1,i)\),其中 \(m(l, r)\) 表示把 \(l\)\(r\) 之间的 \(a[i]\) 变为相同需要的最小数,可以线性预处理。

还有一种思维复杂度和时间复杂度更高的做法,\(f[i][k][last]\) 表示前 \(i\) 个数相邻不同的数量小于 \(k\) 且修改后 \(a[i]\) 的值是 \(last\) 的最小操作数,转移就有点复杂了。

官方题解中有一个观察,修改操作可以用删除替换,不过好像区别不大?官方题解中还提供了一种复杂度更低的做法,二分答案,然而我并不知道怎么判是否可行(我看了差不多十份代码也没找到用二分的)。

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
// -----------------------------------------------------------------------------
const int N = 100 + 5, M = 1000 + 5;
int a[N], f[N][N];
int d[M], m[N];

void up(int& x, int y) { x = min(x, y); }

void solve() {
int n, K; cin >> n >> K;
FOR (i, 0, n) scanf("%d", a + i);
memset(f, 0x3f, sizeof f);
FOR (i, 0, K + 1) f[0][i] = 0;
FOR (i, 1, n) {
int _m = 0;
FORD (j, i, -1) {
_m = max(_m, d[a[j]]++);
m[j] = (i - j) - _m;
}
FOR (j, 0, i + 1) --d[a[j]];
f[i][0] = m[0];
FOR (k, 1, K + 1) {
f[i][k] = f[i][k - 1];
FOR (j, 0, i)
up(f[i][k], f[j][k - 1] + m[j + 1]);
}
}
printf("%d\n", f[n - 1][K]);
}

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
solve();
}
}

Teach Me

考虑问题的反面,有多少对不能 mentor。对于一个人 x,y 不能 mentor 他的充要条件是 y 是 x 的子集。然后枚举子集,哈希后用 map 统计一下就好了。

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
// -----------------------------------------------------------------------------
const int N = 5E4 + 100;
map<LL, int> mp;

void solve() {
mp.clear();
vector<LL> a, x;

int n, S; cin >> n >> S;
FOR (i, 0, n) {
x.clear();
int k; scanf("%d", &k);
FOR (_, 0, k) { int t; scanf("%d", &t); x.push_back(t); }
sort(x.begin(), x.end());
FOR (j, 1, 1 << x.size()) {
LL v = 0;
FOR (k, 0, x.size()) if ((j >> k) & 1) v = v * 1001 + x[k];
++mp[v];
if (j == (1 << x.size()) - 1) a.push_back(v);
}
}
LL ans = 0;
for (LL& v: a) ans += n - mp[v];
cout << ans << endl;
}

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
solve();
}
}

Round G

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050e02

Book Reading

考虑被撕掉的每一页,当询问是页数的因数时会减少对答案的贡献。预处理每个数的因数,统计一下就好了。

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
// -----------------------------------------------------------------------------
const int N = 1E5 + 100;
vector<int> a[N];
int c[N], d[N];

int main() {
FOR (i, 1, N)
for (int j = i; j < N; j += i)
a[j].push_back(i);
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
int n, m, Q; cin >> n >> m >> Q;
FOR (i, 0, m) scanf("%d", d + i);
FOR (i, 0, m) for (int t: a[d[i]]) ++c[t];
LL ans = 0;
FOR (_, 0, Q) {
int x; scanf("%d", &x);
ans += n / x - c[x];
}
printf("%lld\n", ans);
FOR (i, 0, m) for (int t: a[d[i]]) --c[t];
}
}

The Equation

从高到低枚举答案二进制的每一位,如果枚举到的这一位能是 1,那么就放 1,否则只能放 0。判断某一位是不是能放 1,只要让剩下的那些没确定的位放最优(也就是能让异或和结果尽可能小的),再判断是否满足条件即可。

注意数据范围,不要在运算过程中爆 long long。

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
// -----------------------------------------------------------------------------
const int N = 1000 + 100, C = 50;
LL c[C], d[C];

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
memset(c, 0, sizeof c);
printf("Case #%d: ", Ca);
LL n, M; scanf("%lld%lld", &n, &M);
FOR (_, 0, n) {
LL t; scanf("%lld", &t);
FOR (i, 0, C) if ((t >> i) & 1) ++c[i];
}
FOR (i, 0, C) d[i] = min(c[i], n - c[i]) << i;
FOR (i, 1, C) d[i] += d[i - 1];
if (d[C - 1] > M) { puts("-1"); continue; }
LL ans = 0, S = 0;
FORD (i, C - 1, -1) {
if (S + ((n - c[i]) << i) + (i ? d[i - 1] : 0) <= M) {
ans += 1LL << i;
S += (n - c[i]) << i;
} else S += c[i] << i;
}
assert(S <= M);
printf("%lld\n", ans);
}
}

Shifts

\(O(3^{20})\) 显然不怎么行,考虑两边相遇。分别处理 \(O(3^{10})\),把每种组合看成坐标的一个点,对于左边的每一个点,需要知道在右边的某个矩形里的点的个数。做法就是按照一维排序,另一维用数据结构维护,代码中用了 pb_ds 里的平衡树,离散化用树状数组或者用 cdq 分治也行。

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
// -----------------------------------------------------------------------------
const int N = 20 + 10;
using VLL = vector<pair<LL, LL>>;
VLL L, R;
pair<LL, LL> a[N];

void go(const VLL& a, pair<LL, LL> s, VLL& ret, int k) {
if (k == a.size()) { ret.push_back(s); return; }
go(a, {s.first + a[k].first, s.second + a[k].second}, ret, k + 1);
go(a, {s.first, s.second + a[k].second}, ret, k + 1);
go(a, {s.first + a[k].first, s.second}, ret, k + 1);
}

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using Tree = tree<pair<LL, int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
Tree t;

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
L.clear(); R.clear(); t.clear();
int n; LL H;
cin >> n >> H;
FOR (i, 0, n) scanf("%lld", &a[i].first);
FOR (i, 0, n) scanf("%lld", &a[i].second);
go(VLL(a, a + n / 2), {0, 0}, L, 0);
go(VLL(a + n / 2, a + n), {0, 0}, R, 0);
sort(L.begin(), L.end());
sort(R.begin(), R.end(), greater<>());
LL k = 0, ans = 0;
int clk = 0;
for (auto& x: L) {
while (k < R.size() && R[k].first + x.first >= H) t.insert({R[k++].second, clk++});
ans += k - t.order_of_key({H - x.second, -1});
}
cout << ans << endl;
}
}