Atcoder Beginner Contest 399 题解

发表于 2025-03-30 更新于 2025-03-31 分类于 Atcoder 阅读次数：本文字数： 11k

这场的 E 听取 WA 声一片。

C

题意

给定一个 \(n\) 点 \(m\) 边的图，输出让这张图成为森林所需要删去的边数。

题解

森林即很多棵树的集合，不能有环，加边时判断新边能否与原来的图形成环可以用并查集来判断。

另一种做法是对于每个联通块 DFS，开一个 vis 数组，对于没有访问过的边 DFS 即可，遇到没有访问过的点，说明这条边可以保留，从 \(m\) 中减去不能保留的边即可。

DSU 做法：

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

struct DSU {
    int n;
    vector<int> p, sz;
    DSU(int n_) {
        n = n_;
        init(n);
    }
    void init(int n) {
        p.resize(n + 1);
        sz.resize(n + 1, 1);
        iota(p.begin() + 1, p.end(), 1);
    }
    int find(int x) {
        while (x != p[x]) {
            x = p[x] = p[p[x]];
        }
        return x;
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (sz[x] > sz[y]) {
            swap(x, y);
        }
        sz[y] += sz[x];
        p[x] = y;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sz[find(x)]; }
};

void solve() {
    int n, m;
    cin >> n >> m;
    DSU dsu(n);
    int cnt = 0;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        if (!dsu.same(x, y)) {
            dsu.merge(x, y);
        } else {
            cnt++;
        }
    }
    cout << cnt << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

DFS 做法：

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<bool> vis(n + 1);
    vector<vector<int>> e(n + 1);
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    int ans = m;
    auto dfs = [&](auto dfs, int x, int fa) -> void {
        vis[x] = true;
        for (auto y : e[x]) {
            if (y == fa) {
                continue;
            }
            if (!vis[y]) {
                dfs(dfs, y, x);
                ans--;
            }
        }
    };
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs(dfs, i, 0);
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D

题意

给定一个长度为 \(2n\) 的数组，其中数字 1 到 \(n\) 都恰好有两个，求满足一下条件的 \((a,b)\) 的数量：两个 \(a\) 出现的位置不相邻、两个 \(b\) 出现的位置不相邻、且可以通过交换任意 \(a,b\) 使得两个 \(a\) 相邻，两个 \(b\) 也相邻。

题解

观察到只有两种情况能满足条件：“ab...ab” 和 “ab...ba”，对于前一种情况，第一个 \(b\) 和第二个 \(a\) 是可以相邻的，对于后一种情况，两个 \(b\) 不能相邻，开一个 map 维护满足这种条件的数的位置即可。

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n;
    cin >> n;
    n *= 2;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    map<array<int, 2>, int> mp;
    int ans = 0;
    for (int i = 1; i < n; i++) {
        if (mp[{a[i], a[i + 1]}]) {
            ans++;
        } else if (mp[{a[i + 1], a[i]}] && i - mp[{a[i + 1], a[i]}] >= 2) {
            ans++;
        }
        mp[{a[i], a[i + 1]}] = i + 1;
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E

题意

给定两个长度相等的字符串 \(S,T\)，对于每一个位置 \(i\)，可以进行任意次操作：将所有字母 \(s_i\) 换成任意一个字母。最终需要 \(S,T\) 完全相等，输出操作次数或 -1 代表不可能。

题解

最受诟病的一道题，细节点非常多。

首先注意到可以将 \(s_i\) 与 \(t_i\) 连边，代表 \(s_i\) 需要变成 \(t_i\)，此时我们可以发现第一种不可能的情况：对于字母 \(a\)，如果它同时指向了两个字母（包括自身），就不可能满足条件。

连好边后，我们可以从出度为 0 的节点开始，进行类似拓扑的操作依次更新，这样就是操作次数了。那么，是不是只要有环就不行呢？你会发现你过不了样例四，对于 s = "abac", t = "bcba"，虽然连成了一个环，但是可以把其中任意一个字符改为不为 "abcd" 的任意字母，这样就可以把环解开成链了。对于一条链，需要的操作次数就是边数

然而，如果环的长度太大，使得 26 个字母全部出现了，就不能进行这样的拆环操作了，这是我们第二种不可能的情形。

还有一种环是比较特殊的，如下图（这里假设字母的数量均在图里，没有别的字母可以修改）：

在这种情况下，虽然有环，也没有节点可以替代，但是 A，C 两点都指向 B，可以先把 C 变成 A，就变成了一条链的情况了，最后再让 AC 一起变成 B，所需的操作也是边数。可见，只有连通块内所有节点都在环上时，答案需要额外加一。

接下来可以考虑一下怎么实现了：先特判一下不存在的情况，给每个字母维护一个指向的字母，如果冲突就不存在；同时标记用过的字母，如果使用了全部 26 个字母，那么在 26 个点、26 条边的情况下一定会形成环，我们需要考虑 26 个字母是不是全部在环上：所以还需要每个节点的度数来判定——维护入度就好，只要有一个字母入度不为 1 就行。

接下来所有情况就有解了，我们采用并查集来维护连通块，然后遍历每一个连通块，根据度数判定含不含有环，无环的话答案加上边数，否则答案加上边数加一。

这样提交上去发现还是有四个点没过，这是因为如果 26 个字母都是自环，会被错误地判定为无解，特判一下 s == t 即可。

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

struct DSU {
    int n;
    vector<int> p, sz;
    DSU(int n_) {
        n = n_;
        init(n);
    }
    void init(int n) {
        p.resize(n + 1);
        sz.resize(n + 1, 1);
        iota(p.begin() + 1, p.end(), 1);
    }
    int find(int x) {
        while (x != p[x]) {
            x = p[x] = p[p[x]];
        }
        return x;
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (sz[x] > sz[y]) {
            swap(x, y);
        }
        sz[y] += sz[x];
        p[x] = y;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sz[find(x)]; }
};

void solve() {
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    s = " " + s, t = " " + t;
    if (s == t) {  // 每个字母都有自环，需要特判
        cout << 0 << "\n";
        return;
    }
    vector<int> e(27);
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = s[i] - 'a' + 1;
        b[i] = t[i] - 'a' + 1;
    }
    vector<int> deg(27);
    for (int i = 1; i <= n; i++) {
        if (e[a[i]] == 0) {
            e[a[i]] = b[i];
            deg[b[i]]++;
        } else if (e[a[i]] != b[i]) {
            cout << -1 << "\n";
            return;
        }
    }
    bool ok = false;
    for (int i = 1; i <= 26; i++) {
        if (deg[i] != 1) {
            ok = true;
            break;
        }
    }
    if (!ok) {
        cout << -1 << "\n";
        return;
    }
    DSU dsu(26);
    int ans = 0;
    for (int i = 1; i <= 26; i++) {
        if (e[i] != 0) {
            if (e[i] != i) {
                ans++;
                dsu.merge(e[i], i);
            }
        }
    }
    vector<vector<int>> groups(27);
    for (int i = 1; i <= 26; i++) {
        groups[dsu.find(i)].push_back(i);
    }
    for (auto g : groups) {
        int is_ring = 1;
        for (auto x : g) {
            if (deg[x] != 1) {
                is_ring = 0;
            }
        }
        if (is_ring && g.size() > 1) {
            ans++;
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F

题意

给定数组 \(A\)，求 \(\displaystyle \sum_{1\leq l\leq r\leq N} \Bigg(\sum_{l\leq i\leq r} A_i\Bigg)^K\)，模 998244353 ，\(N\le 2\times10^5,K\le 10\)

题解

里面的区间和很难不想到前缀和，设前缀和为 \(P\)，继续推导有： \[ \begin{align*}&\sum_{1\leq l\leq r\leq N} \Bigg(\sum_{l\leq i\leq r} A_i\Bigg)^K \\\\ &=\sum_{r=1}^{n}\sum_{l=1}^r(P_r-P_{l-1})^K -----前缀和\\\\ &=\sum_{r=1}^n\sum_{l=1}^r\sum_{j=0}^k(-1)^{k-j}\begin{pmatrix}k\\j \end{pmatrix}P_r^jP_{l-1}^{k-j} --二项式定理\\\\ &=\sum_{r=1}^n\sum_{j=0}^k(-1)^{k-j}\begin{pmatrix}k\\j \end{pmatrix}P_r^j\sum_{l=1}^rP_{l-1}^{k-j}--求和内与求和变量无关交换求和次序\\\\ &=\sum_{i=1}^n\sum_{j=0}^k(-1)^{k-j}\begin{pmatrix}k\\j \end{pmatrix}P_i^j\sum_{t=0}^{i-1}P_{t}^{k-j}--求和变量名替换 \end{align*} \] 预处理组合数，前缀和，前缀和的幂，前缀和的幂的前缀和即可。这里注意 \(P^0_{i}\) 要处理为 1，因为在 \(t = 0\) 时上式是有意义的。

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

template <class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}
template <int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 x) : x{norm(x % getMod())} {}

    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) { Mod = Mod_; }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const { return x; }
    explicit constexpr operator int() const { return x; }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & { return *this *= rhs.inv(); }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};
template <>
int MInt<0>::Mod = 998244353;

template <int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P = 998244353;
using Z = MInt<P>;  // 静态模数，题目给定模数
using D = MInt<0>;  // 动态模数，可以 D::setMod(x) 改变

struct Comb {
    int n;
    std::vector<Z> _fac;
    std::vector<Z> _invfac;
    std::vector<Z> _inv;

    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() { init(n); }

    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);

        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }

    Z fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    Z inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    Z binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
} comb(10);

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    vector<vector<Z>> p(n + 1, vector<Z>(k + 1, Z(1))),
        p2(n + 1, vector<Z>(k + 1, Z(1)));
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[i][1] = p[i - 1][1] + a[i];
        p[i][0] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            p[i][j] = p[i][j - 1] * p[i][1];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            p2[i][j] = p2[i - 1][j] + p[i][j];
        }
    }

    Z ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            if ((k - j) % 2 == 1) {
                ans += Z(-1) * comb.binom(k, j) * p[i][j] * p2[i - 1][k - j];
            } else {
                ans += Z(1) * comb.binom(k, j) * p[i][j] * p2[i - 1][k - j];
            }
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}