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

A – Is it rated?

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int r, c;
    cin >> r >> c;

    if (c == 1)
    {
        if (r >= 1600 && r <= 2999)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    else
    {
        if (r >= 1200 && r <= 2399)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}

B – Not All

算法：

    模拟。

思路：

    无。

关键代码：

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

    ll ans = 0;
    vector<int> st(m + 1, 0);
    for (int i = 0; i < n; ++i)
    {
        st[a[i]] = 1;

        int now = 1;
        while (now <= m && st[now])
            ++now;

        if (now == m + 1)
        {
            ans = n - i;
            break;
        }
    }

    cout << ans << endl;
}

C – Sum of Product

算法：

    前缀和，推公式。

思路：

    \(\sum_{1\le i<j\le N} A_i A_j \Rightarrow \sum_{1\le i\le N – 1} A_i \sum_{i + 1\le j\le N} A_j\)

关键代码：

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

    vector<ll> s(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + a[i];

    ll ans = 0;
    for (ll i = 1; i < n; ++i)
        ans += a[i] * (s[n] - s[i]);

    cout << ans << endl;
}

D – Escape Route

算法：

    \(bfs\)，最短路。

思路：

    跑一个 \(bfs\) 多源最短路，记录一下路径即可。

关键代码：

void miyan()
{
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    for (int i = 0; i < n; ++i)
        cin >> s[i];

    vector pre(n, vector<pii>(m));
    vector st(n, vector<int>(m, 0));
    auto bfs = [&]() -> void
    {
        queue<pii> q;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (s[i][j] == 'E')
                {
                    q.push({i, j});
                    st[i][j] = 1;
                    pre[i][j] = {-1, -1};
                }
            }
        }

        while (q.size())
        {
            auto [x, y] = q.front();
            q.pop();

            for (int i = 0; i < 4; ++i)
            {
                int a = x + dx[i], b = y + dy[i];

                if (a >= 0 && a < n && b >= 0 && b < m && !st[a][b] && s[a][b] != '#')
                {
                    st[a][b] = 1;
                    pre[a][b] = {x, y};
                    q.push({a, b});
                }
            }
        }
    };

    bfs();

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (s[i][j] == '.')
            {
                auto [x, y] = pre[i][j];

                if (x == i)
                {
                    if (y < j)
                        s[i][j] = '<';
                    else
                        s[i][j] = '>';
                }
                else
                {
                    if (x < i)
                        s[i][j] = '^';
                    else
                        s[i][j] = 'v';
                }
            }
        }
    }

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

E – Fruit Lineup