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

A – OS Versions

算法：

    模拟。

思路：

    无。

关键代码：

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

    map<string, int> m;
    m["Ocelot"] = 1;
    m["Serval"] = 2;
    m["Lynx"] = 3;

    if (m[s] >= m[t])
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

B – The Odd One Out

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    string s;
    cin >> s;

    map<char, int> m;
    for (auto c : s)
        ++m[c];

    for (auto [x, y] : m)
        if (y == 1)
            cout << x << endl;
}

C – Upgrade Required

算法：

    模拟，堆。

思路：

    无。

关键代码：

void miyan()
{
    int n, Q;
    cin >> n >> Q;

    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> q;
    q.push({1, n, 1});

    while (Q--)
    {
        int x, y;
        cin >> x >> y;

        ll ans = 0;
        int cur = 0;
        while (q.top()[0] <= x)
        {
            auto [l, r, cnt] = q.top();
            q.pop();

            int t = min(x, r);
            ans += (t - l + 1) * cnt;
            cur += (t - l + 1) * cnt;

            if (t < r)
                q.push({t + 1, r, 1});
        }

        if (cur)
            q.push({y, y, cur});

        cout << ans << endl;
    }
}

D – Pop and Insert

算法：

    贪心。

思路：

    贪心策略：将所有字符都插入到拥有最多相同字符块的旁边，定义最多相同字符块为 \(G\)，字符为 \(C\)。

• 如果一个字符与 \(C\) 不同，那么只需要一次操作就可以移动到 \(G\) 旁边。
• 如果相同就需要两次操作。

    双指针分块即可。

关键代码：

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

    ll cnt0 = ranges::count(s, '0');
    ll cnt1 = n - cnt0;
    ll maxx0 = 0, maxx1 = 0;
    for (int i = 0, j; i < n; ++i)
    {
        j = i + 1;
        while (j < n && s[j] == s[i])
            ++j;

        if (s[i] - '0')
            maxx1 = max(maxx1, 1ll * j - i);
        else
            maxx0 = max(maxx0, 1ll * j - i);

        i = j - 1;
    }

    cout << min((cnt1 - maxx1) * 2 + cnt0, (cnt0 - maxx0) * 2 + cnt1) << endl;
}

E – Closest Moment

    三分还没补。

F – Clearance

    线段树还没补。