Google Code Jam Qualification Round 2022 Tutorial

Contents

Info
Problems

Info

Practice Link
Code Repo Link
Score: 71
Rank: 3630

Problems

Punched Cards

题意：

给出和，按指定规则画图。

思路：

模拟即可。

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

void run() {
    int n, m;
    cin >> n >> m;

    auto res = vector<string>();

    for (int i = 0; i < n * 2 + 1; i++) {
        string s = "";
        string t = i % 2 ? "|." : "+-";
        for (int j = 0; j < m * 2 + 1; j++) {
            s += t[j & 1];
        }

        res.push_back(s);
    }

    res[0][0] = res[0][1] = res[1][0] = res[1][1] = '.';

    for (const auto &s : res) {
        cout << s << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);

    int _T;
    cin >> _T;
    for (int i = 1; i <= _T; ++i) {
        cout << "Case #" << i << ":\n";
        run();
    }

    return 0;
}

3D Printing

题意：

有台打印机，每台打印机需要种墨水，给出每台打印机中每种墨水的含量。

现在要用每个打印机分别打印一个 logo，打印 logo 需要单位的墨水，颜色不限，但是每种颜色的用量需要一致。

问每种颜色的墨水用量是多少，能够满足要求。

思路：

贪心即可。

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

void run() {
    constexpr int Max = 1000000;
    auto vec = vector<vector<int>>(4, vector<int>(3, 0));
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            int x;
            cin >> x;
            vec[j][i] = x;
        }
    }

    auto res = vector<int>();
    for (int i = 0; i < 4; i++) {
        res.push_back(*min_element(all(vec[i])));
    }

    int tot = accumulate(all(res), 0);

    if (tot < Max) {
        cout << "IMPOSSIBLE\n";
        return;
    }

    for (int i = 0; i < 4; i++) {
        if (tot > Max) {
            if (res[i] <= tot - Max) {
                tot -= res[i];
                res[i] = 0;
            } else {
                res[i] -= tot - Max;
                tot = Max;
            }
        }

        cout << res[i] << " \n"[i == 3];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);

    int _T;
    cin >> _T;
    for (int i = 1; i <= _T; ++i) {
        cout << "Case #" << i << ": ";
        run();
    }

    return 0;
}

d1000000

题意：

有个骰子，第个骰子是维的，即含有数字。

现在目标是要将一部分骰子连起来，并且每个骰子向上的那一面的数字是个顺子，但是不要求从开始。

思路：

贪心
先不断往右边扩
右边扩不了了再往左边扩

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

void run() {
    int n;
    cin >> n;
    auto vec = vector<int>(n, 0);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        vec[i] = x;
    }

    sort(all(vec));

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

    cout << r - l + 1 << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);

    int _T;
    cin >> _T;
    for (int i = 1; i <= _T; ++i) {
        cout << "Case #" << i << ": ";
        run();
    }

    return 0;
}

Chain Reactions

题意：

有个反应堆，每个反应堆的 fun 值为。

部分反应堆能连起来，发生连锁反应。

连锁反应产生的 fun 值是发生反应的反应堆集合中的 fun 值的最大值。

但是一个反应堆只能发生一次反应，如果被连锁反应多次触发，在第二次及后续中被触发时它不会发生反应。

连锁反应的关系是一个树，不是图。

现在能手动触发某个反应堆，使其发生反应，如果该反应堆后续连着另外的反应堆，那么就会发生连锁反应。

问以最优的方案去手动触发反应堆，能获得的最大 fun 值之和是多少？

思路：

考虑树形 dp。

每次将最小的 fun 值往父亲合并。

其它儿子的值直接加到答案中。

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head
const int N = 1e5 + 10;
int n, a[N], f[N];
vector<vector<int>> G;
ll res;

ll dfs(int rt) {
    if (G[rt].empty()) {
        return a[rt];
    }

    vector<int> f;
    for (const auto &son : G[rt]) {
        f.push_back(dfs(son));
    }

    sort(all(f));

    res += accumulate(all(f), 0ll) - f[0];
    return max(a[rt], f[0]);
}

void run() {
    cin >> n;
    G.clear();
    G.resize(n + 1);
    res = 0;

    for (int i = 1; i <= n; i++) cin >> a[i];

    auto rts = vector<int>();
    for (int i = 1; i <= n; i++) {
        cin >> f[i];

        if (f[i]) {
            G[f[i]].push_back(i);
        } else {
            rts.push_back(i);
        }
    }

    for (const auto &rt : rts) {
        res += dfs(rt);
    }

    cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);

    int _T;
    cin >> _T;
    for (int i = 1; i <= _T; ++i) {
        cout << "Case #" << i << ": ";
        run();
    }

    return 0;
}

Twisty Little Passages

留坑。

Last update: April 27, 2022
Created: April 14, 2022