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

A – Too Many Requests

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        if (i <= m)
            cout << "OK" << endl;
        else
            cout << "Too Many Requests" << endl;
    }
}

B – N – 1

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (auto &x : a)
        cin >> x;

    int s = accumulate(all(a), 0);
    for (int i = 0; i < n; ++i)
    {
        if (s - a[i] == m)
        {
            cout << "Yes" << endl;
            return;
        }
    }

    cout << "No" << endl;
}

C – Odd One Subsequence

算法：

    贡献法，组合数学。

思路：

    考虑每个元素的贡献，对于一个出现次数大于等于 \(2\) 次的元素，元素记为 \(val\)，出现次数记为 \(x\)，其就可当作三元组的前两个元素，那么使用 \(val\) 当做三元组中出现两次的三元组个数就为 \(C_{x}^{2} = C_{x}^{x – 2}\)，那么再与剩余其他不同元素可构成的三元组个数为 \(C_{x}^{x – 2} * (n – x) = x * (x – 1) / 2 * (n – x)\)。

    使用哈希表存每个元素出现次数即可。

关键代码：

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

    map<int, ll> m;
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;
        ++m[x];
    }

    ll ans = 0;
    for (auto [x, y] : m)
    {
        ll cnt = y * (y - 1ll) / 2ll;

        ans += cnt * (n - y);
    }

    cout << ans << endl;
}

D – On AtCoder Conference

算法：

    双指针。

思路：

    点多，人少，考虑枚举人。

    将在同一点的人合并。

    由于点比人多很多那么就会有很多连续的空点。那么这些空点的答案肯定是一样的。

    考虑将所有人都存到数组内，求出当前的人所在的点 \(x\) 满足大于 \(C\) 时的答案，那么上一个存在人的点 \(y\) 到 \(x – 1\) 的答案都是一样的。

    下一个存在点的人也可完全继承上一个的状态，删去 \(x\) 点即可，双指针处理。

关键代码：

void miyan()
{
    ll n, m, c;
    cin >> n >> m >> c;
    map<ll, ll> hash;
    for (int i = 0; i < n; ++i)
    {
        ll x;
        cin >> x;
        ++hash[x];
    }

    vector<pair<ll, ll>> a;
    for (auto [x, y] : hash)
        a.push_back({x, y});

    n = a.size();
    ll ans = 0;
    ll cur = 0;
    for (ll i = 0, j = 0; i < n; ++i)
    {
        while (cur < c)
        {
            cur += a[j % n].second;
            ++j;
        }

        ll t = a[i].first;
        if (i)
            t -= a[i - 1].first;
        else
            t = t + m - a[n - 1].first;

        ans += t * cur;

        cur -= a[i].second;
    }

    cout << ans << endl;
}

E – Hit and Away

算法：

    最短路，次短路。

思路：

    安全点\(1\) ~ 危险点 ~ 安全点\(2\) = 安全点\(1\) ~ 危险点 + 安全点\(2\) ~ 危险点。

    对于每个危险点，使用 \(bfs\) 求出其到达安全点的最短路径和次短路径，这两个路径来源的安全点要不一样，可以使用一个数组标注。

关键代码：

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

    string s;
    cin >> s;

    s = ' ' + s;

    vector<int> dist1(n + 1, 1e9), dist2(n + 1, 1e9), from(n + 1, 0);
    auto bfs = [&]() -> void
    {
        queue<array<int, 3>> q;
        for (int i = 1; i <= n; ++i)
        {
            if (s[i] == 'S')
            {
                q.push({i, 0, i});
                dist1[i] = 0;
                from[i] = i;
            }
        }

        while (q.size())
        {
            auto [u, d, f] = q.front();
            q.pop();

            for (auto v : g[u])
            {
                if (dist1[v] == 1e9)
                {
                    dist1[v] = d + 1;
                    from[v] = f;
                    q.push({v, d + 1, f});
                }
                else if (dist2[v] == 1e9 && from[v] != f)
                {
                    dist2[v] = d + 1;
                    q.push({v, d + 1, f});
                }
            }
        }
    };

    bfs();

    for (int i = 1; i <= n; ++i)
        if (s[i] == 'D')
            cout << dist1[i] + dist2[i] << endl;
}

F – Shortest Path Query

    还没补。