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

A – Scary Fee

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    ll x, c;
    cin >> x >> c;

    cout << ll(x / (1000ll + c)) * 1000ll << endl;
}

B – Locked Rooms

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (auto &x : a | views::drop(1))
        cin >> x;

    vector<int> st(n + 1, 0);
    st[0] = st[n] = 1;
    for (int i = 1; i <= n; ++i)
    {
        if (!a[i])
            st[i] = 1;
        else
            break;
    }

    for (int i = n; i >= 1; --i)
    {
        if (!a[i])
            st[i - 1] = 1;
        else
            break;
    }

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

    cout << ans << endl;
}

C – Lock All Doors

算法：

    贪心。

思路：

    无。

关键代码：

void miyan()
{
    int n, r;
    cin >> n >> r;
    vector<int> a(n + 1);
    for (auto &x : a | views::drop(1))
        cin >> x;

    int L = 1, R = n;
    while (L <= n && a[L])
        ++L;
    while (R >= 1 && a[R])
        --R;

    if (L > R)
    {
        cout << 0 << endl;
        return;
    }

    L = min(L, r + 1);
    R = max(R, r);

    ll ans = 0;
    for (int i = L; i <= R; ++i)
        ans += a[i] + 1;

    cout << ans << endl;
}

D – Long Waiting

算法：

    贪心，堆。

思路：

    无。

关键代码：

void miyan()
{
    ll n, k;
    cin >> n >> k;
    vector<array<ll, 3>> a(n);
    for (auto &[x, y, z] : a)
        cin >> x >> y >> z;

    vector<ll> ans(n);
    priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<>> q;
    int pos = 0;
    ll cnt = 0;
    ll time = 0;
    while (pos < n || q.size())
    {
        while (pos < n && cnt < k && a[pos][2] + cnt <= k)
        {
            if (time < a[pos][0])
                time = a[pos][0];

            q.push({time + a[pos][1], pos, a[pos][2]});
            cnt += a[pos][2];
            ans[pos++] = time;
        }

        if (q.size())
        {
            time = q.top()[0];

            while (q.size() && q.top()[0] <= time)
            {
                auto t = q.top();
                q.pop();

                cnt -= t[2];
            }
        }
    }

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

E – Sum of Subarrays

算法：

    前缀和，推公式。

思路：

    考虑每个元素对答案的贡献。

    不难发现对于一个区间内的每个元素其对答案的贡献为：

\((i – l + 1) \cdot (r – i + 1) \cdot a[i]\)

    全部元素和为：

\(\sum_{i=l}^{r} (i – l + 1) \cdot (r – i + 1)\cdot a[i]\)

    推导：

\( \sum_{i=l}^{r} [i \cdot r – i ^ 2 + i – l \cdot r + i \cdot l – l + r – i + 1 ] \cdot a[i] \)

\( \sum_{i=l}^{r} [(l + r) \cdot i -i^{2} + r – l – l \cdot r + 1] \cdot a[i] \)

\( \sum_{i=l}^{r} (l + r) \cdot i \cdot a[i] + \sum_{i=l}^{r} i^{2} \cdot a[i] + \sum_{i=l}^{r} (r – l – l \cdot r + 1) \cdot a[i] \)

\( (l + r) \cdot \sum_{i=l}^{r} i \cdot a[i] + \sum_{i=l}^{r} i^{2} \cdot a[i] + (r – l – l \cdot r + 1) \cdot \sum_{i=l}^{r} a[i] \)

    通过以上式子可知，只需维护三个前缀和即可。

关键代码：

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

    vector<ll> s1(n + 1, 0), s2(n + 1, 0), s3(n + 1, 0);
    for (ll i = 1; i <= n; ++i)
    {
        s1[i] = s1[i - 1] + a[i];
        s2[i] = s2[i - 1] + i * a[i];
        s3[i] = s3[i - 1] + i * i * a[i];
    }

    while (q--)
    {
        ll l, r;
        cin >> l >> r;

        ll ans = (l + r) * (s2[r] - s2[l - 1]) - (s3[r] - s3[l - 1]);
        ans += (r - l - l * r + 1) * (s1[r] - s1[l - 1]);

        cout << ans << endl;
    }
}

F – Loud Cicada

    组合数后面再补。