【题解】Google Kick Start

Posted on Edited on In Disqus:

老年人做点笔试题算了。

注：一切以 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;
    }
}