Google Code Jam Round 1A 2022 Tutorial

Contents

• Info
• Problems
  • Double or One Thing
  • Equal Sum
  • Weightlifting

Info

• Practice Link
• Code Repo Link
• Video: BiliBili, Youtube
• Score: 69
• Rank: 734

Problems

Double or One Thing

题意：

给出一个字符串 ，长度为 ，对于每个字符可以选择是否复制一个并且追加在其之后。

那么一共有 种可能的字符串。

比如上面这个例子，就是将高亮处的字符复制了一份的结果。

要求字典序最小的字符串。

思路：

对于小 case， 最大只有 ，可以构造出所有可能的字符串，然后排序，取第一个即可。

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 dfs(int ix, const string &s, string &t, vector<string> &v) {
    if (ix == s.length()) {
        v.push_back(t);
        return;
    }

    t += s[ix];
    dfs(ix + 1, s, t, v);

    t += s[ix];
    dfs(ix + 1, s, t, v);

    t.pop_back();
    t.pop_back();
}

void run() {
    string s;
    cin >> s;
    vector<string> vec;
    string t = "";
    dfs(0, s, t, vec);
    sort(all(vec));
    cout << vec[0] << endl;
}

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

对于大 case：

我们考虑，假设有一个字符串 ，我们能以 复杂度的 dp 去判断它能否通过 构造出来。

那么我们就贪心去按位构造 ，然后去 check 就行。

如何判断 能否通过 构造出来？

考虑 表示 的前 位和 的前 位是否匹配。

转移有：

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() {
    string s;
    cin >> s;
    int n = s.length();

    const auto check = [&](const string &t) -> int {
        int m = t.length();

        auto f = vector<vector<int>>(n + 1, vector<int>(m + 1, 0));
        f[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s[i - 1] == t[j - 1]) {
                    f[i][j] |= f[i - 1][j - 1];
                    if (j >= 2 && s[i - 1] == t[j - 2]) {
                        f[i][j] |= f[i - 1][j - 2];
                    }
                }
            }
        }

        if (f[n][m]) {
            return 2;
        }

        for (int i = 1; i <= n; i++) {
            if (f[i][m]) {
                return 1;
            }
        }

        return 0;
    };

    string t = "";
    for (int i = 1; i <= n * 2; i++) {
        for (int j = 'A'; j <= 'Z'; j++) {
            t += j;
            int check_code = check(t);

            if (check_code == 0) {
                t.pop_back();
                continue;
            }

            if (check_code == 2) {
                cout << t << endl;
                return;
            }

            break;
        }
    }
}

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

Equal Sum

题意：

交互题。

。

你先给出 个互不相同数，然后 jury 给出 个互不相同（并且与你的 个数也互不相同）数。

你需要将数分成两堆，要求两堆数的和相等。

给出的数的范围是 。

思路：

考虑将 以下的 的幂次的数都给出来。

那么这就已经可以构造出 以下的任何数了。

之后将 jury 给出的 个数放在一起排序，先给出大的数，直到剩余的数小于 ，然后用 的幂次去构造这个数字。

注意给出大的数的过程中要剔除掉 的幂次的数。

Code

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

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

    vector<int> f;
    for (int i = 0; i < 30; i++) {
        f.push_back(1 << i);
    }

    int ix = 1000000001;
    while (f.size() < n) {
        --ix;
        if ((ix & (ix - 1)) == 0) {
            continue;
        }

        f.push_back(ix);
    }

    for (int i = 0; i < n; i++) {
        cout << f[i];
        if (i == n - 1) {
            cout << endl;
        } else {
            cout << " ";
        }
    }

    cout << flush;

    ll sum = accumulate(all(f), 0ll);

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        f.push_back(x);
        sum += x;
    }

    assert(sum % 2 == 0);
    ll tar = sum / 2;

    sort(all(f), greater<int>());

    auto res = vector<int>();

    for (const auto &a : f) {
        if ((a & (a - 1)) == 0) {
            continue;
        }

        if (tar < (1 << 30)) {
            break;
        }

        tar -= a;
        res.push_back(a);
    }

    for (int i = 0; i < 30; i++) {
        if ((tar >> i) & 1) {
            res.push_back(1 << i);
        }
    }

    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
        if (i == res.size() - 1) {
            cout << endl;
        } else {
            cout << " ";
        }
    }

    cout << flush;
}

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) {
        run();
    }

    return 0;
}

Weightlifting

题意：

你是一个举重运动员，你的训练目标是每次将不同重量的圆盘组合套在棍子里。

这个棍子可以视为一个栈。

换句话说，你的训练计划有 个步骤。

每个步骤中要求这个棍子里套着的圆盘组合符合训练计划的要求。

你可以做的操作是往棍子上加一个圆盘或者拿掉一个圆盘。

注意，最后要求棍子上没有圆盘。

求最少的操作次数。

思路：

针对小 case：

维护栈中的顺序，next_permutation 转移，。

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 INF = 0x3f3f3f3f;

// int sol1(int E, int W, vector<vector<int>> &vec) {
//     int pre = 0;
//     vec.push_back({0, 0});

//     int res = 0;

//     for (int i = 1; i <= E + 1; i++) {
//         res += abs(pre - vec[i][1]);
//         pre = vec[i][1];
//     }

//     return res;
// }

struct node {
    vector<int> a;
    int v;
    int calc(const node &pre) {
        int i = 0;
        while (i < a.size() && i < pre.a.size()) {
            if (a[i] != pre.a[i]) {
                break;
            }

            ++i;
        }

        return pre.a.size() - i + a.size() - i;
    }

    bool operator<(const node &other) const {
        return v < other.v;
    }
};

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

    // if (W == 1) {
    //     cout << sol1(E, W, vec) << endl;
    //     return;
    // }

    auto f = vector<vector<node>>(E + 1, vector<node>());
    f[0].push_back(node{.a = {}, .v = 0});

    for (int i = 1; i <= E; i++) {
        auto t = vector<int>();
        for (int j = 1; j <= W; j++) {
            int cnt = vec[i][j];
            if (cnt == 0) {
                continue;
            }

            auto tt = vector<int>(cnt, j);
            t.insert(t.end(), all(tt));
        }

        // for (int o = 0; o < t.size(); o++) {
        //     cout << t[o] << " ";
        // }
        // cout << endl;

        do {
            auto now = node();
            now.a = t;
            now.v = INF;
            for (const auto &_f : f[i - 1]) {
                now.v = min(now.v, _f.v + now.calc(_f));
            }
            f[i].push_back(now);
        } while (next_permutation(all(t)));
    }

    int res = INF;
    for (const auto &_f : f[E]) {
        res = min(res, int(_f.v + _f.a.size()));
    }

    cout << res << endl;
}

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

---

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