链接：https://atcoder.jp/contests/abc399

A – Hamming Distance

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    string s, t;
    cin >> n >> s >> t;

    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        if (s[i] != t[i])
            ++ans;
    }

    cout << ans << endl;
}

B – Ranking with Ties

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<pii> a(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i].first;
        a[i].second = i;
    }

    ranges::sort(a, greater<>());

    vector<int> ans(n);
    int cur = 0;
    int last = -1;
    for (int i = 0; i < n; ++i)
    {
        if (last == -1 || a[i].first != last)
        {
            cur = i + 1;
            last = a[i].first;
        }
        ans[a[i].second] = cur;
    }

    for (auto x : ans)
        cout << x << endl;
}

C – Make it Forest

算法：

    搜索，图论。

思路：

    森林是由多颗树组成。

    \(dfs\) 找出每个连通块的点数和边数，一颗树边数 \(=\) 点数 \(– 1\)，多余的删除，全部需要删除的就是答案。

关键代码：

void miyan()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> st(n + 1, 0);
    int cnt, edge;
    auto dfs = [&](auto &&self, int u, int f) -> void
    {
        st[u] = 1;
        ++cnt;
        edge += g[u].size();
        for (auto v : g[u])
        {
            if (v == f || st[v])
                continue;

            self(self, v, u);
        }
    };

    ll ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (!st[i])
        {
            cnt = 0, edge = 0;
            dfs(dfs, i, 0);
            ans += edge / 2 - (cnt - 1);
        }
    }

    cout << ans << endl;
}

D – Switch Seats

算法：

    模拟。

思路：

    无。

关键代码：

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

    map<int, vector<pair<pii, pii>>> m;
    vector<int> st(n + 1, 1);
    for (int i = 0; i < n + n; ++i)
    {
        int l = -1, r = -1;
        if (i)
        {
            if (a[i] == a[i - 1])
                st[a[i]] = 0;
            l = a[i - 1];
        }
        if (i + 1 < n + n)
        {
            if (a[i] == a[i + 1])
                st[a[i]] = 0;
            r = a[i + 1];
        }

        m[a[i]].push_back({{l, i - 1}, {r, i + 1}});
    }

    ll ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (!st[i])
            continue;

        auto [l, r] = m[i][0];
        auto [L, R] = m[i][1];

        if (l.first != -1 && L.first != -1 && l.first == L.first && st[l.first] && st[L.first] && l.second != L.second)
            ++ans;
        if (l.first != -1 && R.first != -1 && l.first == R.first && st[l.first] && st[R.first] && l.second != R.second)
            ++ans;
        if (r.first != -1 && L.first != -1 && r.first == L.first && st[r.first] && st[L.first] && r.second != L.second)
            ++ans;
        if (r.first != -1 && R.first != -1 && r.first == R.first && st[r.first] && st[R.first] && r.second != R.second)
            ++ans;
    }

    ans >>= 1;

    cout << ans << endl;
}

E – Replace

    先不补了，通过率太恐怖了。

F – Range Power Sum

    组合数学以后再补。