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

A – Status Code

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    if (n <= 299 && n >= 200)
        cout << "Success" << endl;
    else
        cout << "Failure" << endl;
}

B – Unauthorized

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int q;
    cin >> q;

    ll ans = 0;
    bool flag = 0;
    while (q--)
    {
        string s;
        cin >> s;

        if (s == "login")
            flag = 1;
        else if (s == "logout")
            flag = 0;
        else if (s == "private")
        {
            if (!flag)
                ++ans;
        }
    }

    cout << ans << endl;
}

C – K-bonacci

算法：

    前缀和，减法同余。

思路：

    无。

关键代码：

void miyan()
{
    ll n, k;
    cin >> n >> k;

    if (k > n)
    {
        cout << 1 << endl;
        return;
    }

    ll sum = 0;
    vector<ll> a(n + 1);
    for (int i = 0; i <= n; ++i)
    {
        if (i < k)
        {
            a[i] = 1;
            sum += a[i];
        }
        else
        {
            if (i - k - 1 >= 0)
            {
                sum = (sum + a[i - 1]) % MOD;
                sum = (sum - a[i - k - 1] + MOD) % MOD;
            }
            a[i] = sum;
        }
    }

    cout << sum % MOD << endl;
}

D – Logical Filling

算法：

    模拟，分类讨论，双指针。

思路：

    通过题目可以发现 'o' 旁边的 '?' 必须是 '.'，那么先对 'o' 旁边的 '?' 做出替换。

    替换完之和进行分类讨论：

• 如果 \(cnt(o) == k\)，那么直接将全部的 '?' 替换为 '.' 输出即可。
• 如果 \(cnt(o) < k\)，将所有的 '?' 段替换为 “o.” 交替段并且最大化 'o' 的数量，记为 \(tot\)：
  • 如果 \(cnt + tot == k\)，那么必须最大化 'o' 的数量，对于一段 '?' 段：
    • 如果长度为奇数，那么最大化后为 \(“o.o”\)，此段答案只有一种，此段输出全 '?' 即可。
    • 如果长度为偶数，那么最大化后为 \(“o.o.”\) 或者 \(“.o.o”\)，此段答案不止一种，原样输出即可。
  • 如果 \(cnt + tot > k\)，每一段都不确定，每一段都输出 '?' 即可。

关键代码：

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

    for (int i = 0; i < n; ++i)
    {
        if (s[i] == 'o')
        {
            if (i && s[i - 1] == '?')
                s[i - 1] = '.';
            if (i + 1 < n && s[i + 1] == '?')
                s[i + 1] = '.';
        }
    }

    ll cnt = ranges::count(s, 'o');

    if (cnt == k)
    {
        for (auto &c : s)
            c = (c == '?' ? '.' : c);

        cout << s << endl;
        return;
    }

    ll tot = 0;
    for (int i = 0, j = 0; i < n; ++i)
    {
        if (s[i] == '?')
        {
            j = i + 1;
            while (j < n && s[j] == '?')
                ++j;

            tot += (j - i + 1) / 2;

            i = j;
        }
    }

    if (cnt + tot > k)
    {
        cout << s << endl;
        return;
    }

    for (int i = 0, j = 0; i < n; ++i)
    {
        if (s[i] == '?')
        {
            j = i + 1;
            while (j < n && s[j] == '?')
                ++j;

            ll cur = j - i;
            if (cur & 1)
            {
                bool flag = 1;
                for (int k = i; k < j; ++k, flag = !flag)
                    s[k] = (flag ? 'o' : '.');
            }

            i = j;
        }
    }

    cout << s << endl;
}

E – Reachable Set

算法：

    图论，并查集。

思路：

    使用：

• \(dsu\) 维护当前 \(1\) ~ \(k\) 点的集合。
• 有序集合 \(s\) 维护与 \(1\) ~ \(k\) 的点直接相连但是不属于 \(1\) ~ \(k\) 集合中的点。
• 使用 \(cnt\) 维护前 \(1\) ~ \(k\) 点属于几个集合。

    每次加入一个在 \(1\) ~ \(k\) 集合中加入一个新点，都默认加一个集合，再对这个点所相连的边进行分类讨论：

• 如果其属于 \(1\) ~ \(k\) 但是不和当前点在一个集合，就将其合并，集合数减 \(1\)。
• 否者就加入 \(s\) 集合。

    每次都将 \(s\) 中属于 \(1\) ~ \(k\) 的点移除有序集合。

关键代码：

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> p(n + 1);
    for (int i = 1; i <= n; ++i)
        p[i] = i;

    auto find = [&](auto &&self, int x) -> int
    {
        if (x != p[x])
            p[x] = self(self, p[x]);
        return p[x];
    };

    set<int> s;
    ll cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        ++cnt;
        for (auto x : g[i])
        {
            if (x > i)
                s.insert(x);
            else
            {
                int a = find(find, x), b = find(find, i);
                if (a != b)
                {
                    --cnt;
                    p[a] = b;
                }
            }
        }

        while (s.size() && *s.begin() <= i)
            s.erase(s.begin());

        if (cnt != 1)
            cout << -1 << endl;
        else
            cout << s.size() << endl;
    }
}

F – Add One Edge 3

    树的直径以后再补。