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

A - Four Digits

题意

给出一个整数 \(n\) ，以宽度为 4 补前导 0 的格式输出。

• \(0 \le n \le 9999\)

题解

即 printf("%04d", n) 。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    cout << string(4 - (int)s.size(), '0') + s << "\n";
    return 0;
}

B - Failing Grade

题意

给出一个大小为 \(n\) 数组 \(a\) ，计算其中有多少元素小于 \(p\) 。

• \(1 \le n \le 10^5\)
• \(1 \le p \le 100\)
• \(0 \le a_i \le 100\)

题解

模拟。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, p;
    cin >> n >> p;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        ans += (x < p);
    }
    cout << ans << "\n";
    return 0;
}

C - Swiss-System Tournament

题意

有 \(2n\) 个人进行 \(m\) 轮猜拳，每轮猜拳中 \(n\) 对排名相邻的人两两同时进行比赛，每轮比赛结束后更新排名，规则如下：

• 赢更多场的人在前，如果有两个人赢的场数相同，那么编号更小的人在前

给出 \(2n\) 个人在每轮中所出的拳，输出 \(m\) 轮猜拳后 \(1 \sim 2n\) 名的编号。

题解

模拟。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    n *= 2;
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> p(n), win(n);
    iota(p.begin(), p.end(), 0);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j += 2) {
            int x = p[j], y = p[j + 1];
            if (a[x][i] != a[y][i]) {
                if (a[x][i] == 'G') {
                    (a[y][i] == 'C' ? win[x] : win[y]) += 1;
                } else if (a[x][i] == 'C') {
                    (a[y][i] == 'P' ? win[x] : win[y]) += 1;
                } else {
                    (a[y][i] == 'G' ? win[x] : win[y]) += 1;
                }
            }
        }
        sort(p.begin(), p.end(), [&](int x, int y) {
            return win[x] != win[y] ? win[x] > win[y] : x < y;
        });
    }
    for (auto i : p) {
        cout << i + 1 << "\n";
    }
    return 0;
}

D - Between Two Arrays

题意

给出两个大小为 \(n\) 的序列 \(a, b\) ，计算满足以下条件的序列 \(c\) 的个数：

• \(a_i \le c_i \le b_i\)

答案对 \(998244353\) 取模。

• \(1 \le n \le 3000\)
• \(0 \le a_i \le b_i \le 3000\)

题解

设 \(dp[i][j]\) 为第 \(i\) 个数的值为 \(j\) 的序列个数，易得转移方程：

\[dp[i + 1][j] = \sum \limits _{k = 0} ^{j} dp[i][k] \]

该操作可以使用前缀和优化。

代码

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    const int N = 3010;
    vector<vector<Z>> dp(n, vector<Z> (N));
    for (int i = a[0]; i <= b[0]; i++) {
        dp[0][i] = 1;
    }
    for (int j = 1; j < N; j++) {
        dp[0][j] += dp[0][j - 1];
    }
    for (int i = 1; i < n; i++) {
        for (int j = a[i]; j <= b[i]; j++) {
            dp[i][j] += dp[i - 1][j];
        }
        for (int j = 1; j < N; j++) {
            dp[i][j] += dp[i][j - 1];
        }
    }
    cout << dp[n - 1][b[n - 1]].val() << "\n";
    return 0;
}

E - Red and Blue Tree

题意

给出一棵大小为 \(n\) 的树，一个长为 \(m\) 的序列 \(a\) ，一个整数 \(k\) 。

现需要将每条边染为红色或蓝色，问在 \(2^{n - 1}\) 种情况中，满足以下条件的情况个数：

• 走完所有 \(a_i \sim a_{i + 1}\) 所经红蓝边的个数之差为 \(k\)

答案对 \(998244353\) 取模。

• \(2 \le n \le 1000\)
• \(2 \le m \le 100\)
• \(|k| \le 10^5\)

题解

即将途经边的遍历次数分为和差为 \(k\) 的两个子集。

不妨分别设总和、以及两个子集和为 \(s, x, x+ |k|\) ，则有：

\[x + x + |k| = s \]

解得：

\[x = \frac{s - |k|}{2}, x + |k| = \frac{s + |k|}{2} \]

若一个子集和为 \(x\) ，则另一个子集和必为 \(x + |k|\) ，即和为 \(x\) 的情况数亦为和为 \(x + |k|\) 的情况数，所以不妨考虑 \(x + |k| = \frac{s + |k|}{2} \ge 0\) 的方案数，可以用 \(01dp\) 解决。

最后途径边之外的边两种颜色都可以染。

代码

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    k = abs(k);
    vector<int> a(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i];
        --a[i];
    }
    vector<vector<int>> G(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    map<pair<int, int>, int> mp;
    vector<int> fa(n);
    function<void(int, int)> dfs = [&](int u, int p) {
        fa[u] = p;
        for (auto v : G[u]) {
            if (v != p) {
                dfs(v, u);
            }
        }
    };
    for (int i = 0; i + 1 < m; i++) {
        int s = a[i], t = a[i + 1];
        dfs(s, -1);
        vector<int> path;
        for (int u = t; u != -1; u = fa[u]) {
            path.push_back(u);
        }
        for (int j = 0; j + 1 < (int)path.size(); j++) {
            int u = min(path[j], path[j + 1]), v = max(path[j], path[j + 1]);
            ++mp[{u, v}];
        }
    }
    vector<int> v;
    int sum = 0;
    for (auto [edge, times] : mp) {
        v.push_back(times);
        sum += times;
    }
    if ((sum - k) % 2 != 0) {
        cout << 0 << "\n";
        return 0;
    }
    const int N = (sum + k) / 2;
    vector<Z> dp(N + 1);
    dp[0] = 1;
    for (auto val : v) {
        auto next_dp(dp);
        for (int i = 0; i + val <= N; i++) {
            next_dp[i + val] += dp[i];
        }
        dp = next_dp;
    }
    cout << (dp[N] * (binpow(Z(2), n - 1 - (int)v.size()))).val() << "\n";
    return 0;
}

F - Expensive Expense

题意

给出一棵大小为 \(n\) 的树，每条边的权重为 \(c_i\) ，每个点的权重为 \(d_i\) ，定义 \(dis(i, j) = d_j + \sum \limits _{shortest\_path} c_i\) ，输出每个点与距离它最远点间的距离。

• \(2 \le n \le 2 \times 10^5\)
• \(1 \le c_i, d_i \le 10^9\)

题解

树的直径的性质：

• 直径两端点一定是两个叶子结点
• 距离任意点最远的点一定是直径的一个端点
• 对于两棵树，如果一棵树直径两端点为 \((u, v)\) ，另一棵树直径两端点为 \((x, y)\) ，用一条边将两棵树连接，那么新树的直径一定是 \(u, v, x, y\) 中的两个点

所以只需找出树中的任一条直径即可。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<pair<int, int>>> G(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }
    vector<int> d(n);
    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }
    auto dijkstra = [&](int s) {
        vector<long long> dis(n, LLONG_MAX);
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pque;
        pque.emplace(0, s);
        dis[s] = 0;
        while (not pque.empty()) {
            auto [d, u] = pque.top();
            pque.pop();
            if (d != dis[u]) {
                continue;
            }
            for (auto [v, w] : G[u]) {
                if (d + w < dis[v]) {
                    dis[v] = d + w;
                    pque.emplace(d + w, v);
                }
            }
        }
        int u = -1;
        long long cost = -1;
        for (int i = 0; i < n; i++) {
            if (i != s and dis[i] + d[i] > cost) {
                cost = dis[i] + d[i];
                u = i;
            }
        }
        return make_pair(u, dis);
    };
    auto [u, dis] = dijkstra(0);
    auto [v, dis_u] = dijkstra(u);
    auto [null, dis_v] = dijkstra(v);
    for (int i = 0; i < n; i++) {
        long long ans = 0;
        if (i != u) {
            ans = max(ans, dis_u[i] + d[u]);
        }
        if (i != v) {
            ans = max(ans, dis_v[i] + d[v]);
        }
        cout << ans << "\n";
    }
    return 0;
}

G - 222

题意

有序列 \(2, 22, 222, 2222, \dots\) ，给出 \(t\) 次询问，计算第一个整除 \(k_i\) 的数的位置。

• \(1 \le t \le 200\)
• \(1 \le k_i \le 10^8\)

题解

序列中数的通项可以写作： \(\frac{2}{9} (10^n - 1)\) ，所以即寻找最小的 \(n\) ，使得 \(\frac{2}{9} (10^n - 1) \equiv 0 \mod k\) 。

由：

• \(ax \equiv 0 \mod m \longleftrightarrow x \equiv 0 \mod \frac{m}{gcd(m, a)}\)
• \(\frac{x}{b} \equiv 0 \mod m \longleftrightarrow x \equiv 0 \mod bm\)

可将原同余式转化为：

\(10^n \equiv 1 \mod （\frac{9k}{gcd(9k, 2)} = m')\)

由欧拉定理可得， \(10^{\phi(m')} \equiv 1 \mod m'\) ，所以所求的 \(n\) 一定为 \(\phi(m')\) 的因子。

综上，计算出 \(m'\) 和 \(\phi(m')\) ，然后遍历 \(\phi{(m')}\) 的因子即可。

代码

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

int MOD;

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

int phi(int n) {
    int res = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) {
                n /= i;
            }
            res -= res / i;
        }
    }
    if (n != 1) {
        res -= res / n;
    }
    return res;
};

vector<int> divisor(int n) {
    vector<int> div;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            div.push_back(i);
            if (i != n / i) {
                div.push_back(n / i);
            }
        }
    }
    sort(div.begin(), div.end());
    return div;
};

int solve(int m) {
    MOD = m;
    for (auto i : divisor(phi(m))) {
        if (binpow(Z(10), i).val() == 1) {
            return i;
        }
    }
    return -1;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int k;
        cin >> k;
        int m = (9 * k) / gcd(9 * k, 2);
        cout << solve(m) << "\n";
    }
    return 0;
}

参考

https://atcoder.jp/contests/abc222/editorial/2763

https://www.cnblogs.com/Khada-Jhin/p/10195287.html

https://atcoder.jp/contests/abc222/editorial/2764

https://www.cnblogs.com/DarkValkyrie/p/11739566.html