Toyota Programming Contest 2023 Spring Qual B（AtCoder Beginner Contest 290）【A - G】

比赛时只做出了 4 题，挺有教育意义的一场 ABC 。

比赛链接：https://atcoder.jp/contests/abc290/tasks

A - Contest Result

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int sum = 0;
    for (int i = 0; i < m; i++) {
        int b;
        cin >> b;
        --b;
        sum += a[b];
    }
    cout << sum << "\n";

    return 0;
}

B - Qual B

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    string s;
    cin >> s;

    for (int i = 0, cnt = 0; i < n; i++) {
        if (s[i] == 'o' and ++cnt > k) {
            s[i] = 'x';
        }
    }

    cout << s << "\n";

    return 0;
}

C - Max MEX

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (ans == a[i]) {
            ans += 1;
        }
    }
    cout << min(ans, k) << "\n";

    return 0;
}

D - Marking

题解

当 $gcd(d, n) = 1$ 时，答案为 $k \cdot d\ \%\ n$ ；

当 $gcd(d, n) \ne 1$ 时，答案为 $k / {\frac{n}{g}} + k\ \%\ (n / g) * d$ 。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    #define int long long

    int t;
    cin >> t;

    while (t--) {
        int n, d, k;
        cin >> n >> d >> k;
        d %= n;
        k--;

        if (d == 0) {
            cout << k << "\n";
            continue;
        }

        if (gcd(d, n) == 1) {
            cout << k * d % n << "\n";
        } else {
            int g = gcd(d, n);
            cout << (k / (n / g) + k % (n / g) * d) % n << "\n";
        }
    }

    return 0;
}

E - Make it Palindrome

题解

在所有的连续子数组中一共有 $\sum \limits _{i = 1} ^{n} (n +1 - len) \times \lfloor \frac{len}{2} \rfloor$ 个中心对称的数对；

将值相同的数的下标存起来，利用双指针计算合法数对；

总数减去合法数即所求。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    #define int long long

    int n;
    cin >> n;

    vector<vector<int>> pos(n);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        --x;
        pos[x].push_back(i);
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += (n - i + 1) * (i / 2);
    }
    for (auto vec : pos) {
        int l = 0, r = (int)vec.size() - 1;
        while (l < r) {
            if (vec[l] + 1 < n - vec[r]) {
                ans -= (r - l) * (vec[l] + 1);
                l++;
            } else {
                ans -= (r - l) * (n - vec[r]);
                r--;
            }
        }
    }
    cout << ans << "\n";

    return 0;
}

F - Maximum Diameter

题解

$n$ 个结点的树有 $n - 1$ 条边，所以需要首先满足度数和为 $2(n - 1)$ 。

将所有度数 $\ge 2$ 的结点连成一条线，之后将度数为 $1$ 的结点补上，这种构造方法下的树直径最长，长度为 $度数 \ge 2 的结点个数 + 1$ 。

所求即 $\sum \limits _{合法方案} (度数 \ge 2 的结点个数 + 1)$

$= 合法方案数 + \sum \limits _{合法方案} (度数 \ge 2 的结点个数)$

$= 合法方案数 + \sum \limits _{i = 1} ^{n} (X_i \ge 2 的合法方案数)$

$= 合法方案数 + (X_1 \ge 2 的合法方案数) \times n$

$= C_{2n - 3}^{n - 1} + C_{2n - 4}^{n - 1} \times n\ \ \ (插板法)$

代码

#include <bits/stdc++.h>
using namespace std;

constexpr int N = 2e6 + 10;

constexpr int MOD = 998244353;

int norm(int x) { if (x < 0) { x += MOD; } if (x >= MOD) { x -= MOD; } return x; }
template<class T> T binpow(T a, int b) { T res = 1; for (; b; b /= 2, a *= a) { if (b % 2) { res *= a; } } return res; }

struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    int val() const { return x; }
    Z operator-() const { return Z(norm(MOD - x)); }
    Z inv() const { assert(x != 0); return binpow(*this, MOD - 2); }
    Z &operator*=(const Z &rhs) { x = 1LL * x * rhs.x % MOD; return *this; }
    Z &operator+=(const Z &rhs) { x = norm(x + rhs.x); return *this; }
    Z &operator-=(const Z &rhs) { x = norm(x - rhs.x); return *this; }
    Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
    friend Z operator*(const Z &lhs, const Z &rhs) { Z res = lhs; res *= rhs; return res; }
    friend Z operator+(const Z &lhs, const Z &rhs) { Z res = lhs; res += rhs; return res; }
    friend Z operator-(const Z &lhs, const Z &rhs) { Z res = lhs; res -= rhs; return res; }
    friend Z operator/(const Z &lhs, const Z &rhs) { Z res = lhs; res /= rhs; return res; }
};

struct Combination {
    vector<Z> fac, inv;

    Combination(int n) : fac(n), inv(n) {
        fac[0] = 1;
        for (int i = 1; i < n; i++) fac[i] = fac[i - 1] * i;
        inv[n - 1] = fac[n - 1].inv();
        for (int i = n - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1);
    }

    Z C(int n, int m){
        if(m < 0 or m > n) return 0;
        return fac[n] * inv[m] * inv[n - m];
    }

    Z A(int n, int m){
        if(m < 0 or m > n) return 0;
        return fac[n] * inv[n - m];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Combination C(N);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        cout << (C.C(2 * n - 3, n - 1) + C.C(2 * n - 4, n - 1) * n).val() << "\n";
    }

    return 0;
}

G - Edge Elimination

题解

枚举在 $k$ 叉树哪个深度的分支上。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        long long d, k, x;
        cin >> d >> k >> x;

        vector<long long> pw(d + 1);
        pw[0] = 1;
        for (int i = 1; i <= d; i++) {
            pw[i] = pw[i - 1] * k + 1;
        }

        long long ans = 1e18;
        for (int i = d; i >= 0 and pw[i] >= x; i--) {
            long long remain = pw[i] - x, cnt = (i == d ? 0 : 1);
            for (int j = i - 1; j >= 0 and remain > 0; j--) {
                cnt += remain / pw[j];
                remain %= pw[j];
            }
            ans = min(ans, cnt);
        }
        cout << ans << "\n";
    }

    return 0;
}