链接：https://codeforces.com/contest/2128

A. Recycling Center

算法：

    贪心、排序。

思路：

    直接从最小的开始销毁。

关键代码：

void solve()
{
    ll n, c;
    cin >> n >> c;
    vector<ll> a(n);
    for (auto &x : a)
        cin >> x;

    ranges::sort(a, greater<>());

    ll ans = n;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] <= c)
        {
            --ans;
            c /= 2;
        }
    }

    cout << ans << endl;
}

B. Deque Process

算法：

    贪心、构造。

思路：

    一边取一个。

关键代码：

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

    string ans;
    int l = 1, r = n;
    bool flag = 0;
    while (l < r)
    {
        if (flag)
        {
            if (p[l] >= p[r])
            {
                ans += 'L';
                ++l;
            }
            else
            {
                ans += 'R';
                --r;
            }

            flag = !flag;
        }
        else
        {
            if (p[l] <= p[r])
            {
                ans += 'L';
                ++l;
            }
            else
            {
                ans += 'R';
                --r;
            }

            flag = !flag;
        }
    }

    ans += 'L';
    cout << ans << endl;
}

C. Leftmost Below

算法：

    贪心，数学。

思路：

    可以发现构造第 \(i\) 个元素时，前 \(i – 1\) 个元素必然构造出来了。

    定义 \(minn\) 为前 \(i – 1\) 个元素最小值。

    当前构造 \(a[i]\) 你想让前面的元素都加不到值，只给 \(a[i]\) 加，最多加两次

    第一次加 \(x\) 可选范围为 \([1, minn – 1]\)，第二次加 \(x\) 只能选 \(minn\)

    所以每个元素最大为 \(minn * 2 – 1\), 只要大于这个必然构造不出

关键代码：

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

    ll minn = INT_MAX;
    for (int i = 1; i <= n; ++i)
    {
        if (b[i] > minn + minn - 1)
        {
            cout << "NO" << endl;
            return;
        }

        minn = min(minn, b[i]);
    }

    cout << "YES" << endl;
}

D. Sum of LDS

算法：

    \(dp\)、组合数学、贪心。

思路：

    定义 \(dp[i]\) 为所有以 \(i\) 结尾的子数组 \(LDS\) 长度之和，那么就答案为：\(∑dp[i]\)

    由 \(max(p_i, p_i + 1) > p_i + 2\) 可知：
        整个数组几乎是完全递减的，可能会有一些位置递增一下，但不会连续递增两次，既 \(p_i < p_i + 1\) 且 \(p_i + 1 < p_i + 2\)，这样是不满足题目给出的条件的。

    所以一个子数组的 \(LDS\) = 子数组长度 – 子数组上升的个数。

    每次状态转移考虑把所有以 \(i – 1\) 结尾的子数组延长一个元素到 \(i\)

• \(p_i – 1 > p_i:\)
  • 前面每个子数组长度都可 \(+1\)，以 \(i – 1\) 结尾的子数组有 \(i – 1\) 个，再加上 \([i, i]\)，加到一起就是:\(dp[i] = dp[i – 1] + i\)
• \(p_i – 1 < p_i:\)
  • 由于递增了，需要抛弃 \(p[i]\), 所以前面所有的子数组长度都不变，只会新增 \([i, i]\)，所以 \(dp[i] = dp[i – 1] + 1\)

关键代码：

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

    ll ans = 1;
    vector<ll> dp(n + 1);
    dp[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (p[i - 1] > p[i])
            dp[i] = dp[i - 1] + i;
        else
            dp[i] = dp[i - 1] + 1;

        ans += dp[i];
    }

    cout << ans << endl;
}

E1. Submedians (Easy Version)

算法：

    前缀和、二分。

思路：

    判断一个元素可不可以当作数组中某个子数组的中位数：

        通常转换成 \(+-1\) 前缀和，既：如果 \(a[i] >= x\) 就令 \(a[i] = 1\), 反之为 \(-1\)。

    此时只需一个子数组的和 \(>= 0\)，这个数字就为数组某个子数组的中位数。

    证明：

        当 \(n\) 为偶数时，需要 \(n / 2\) 的元素大于等于 \(x, [latex]n – n / 2\) 的元素小于 \(x\)，如果一段区间和大于等于\(0\)，既:

\(pre[r] – pre[l – 1] \geq 0 \;\;\Rightarrow\;\; pre[r] \geq pre[l – 1]\)。

        当 \(n\) 为奇数时，需要 \(n / 2 + 1\) 的元素大于等于 \(x\), \(n – n / 2 – 1\) 的元素小于 \(x\)，如果一段区间和大于等于\(1\)，既:

\(pre[r] – pre[l – 1] >= 1 \Rightarrow pre[r] >= pre[l – 1] + 1\)

但是一个长度为奇数的子数组，其和也必然为奇数，不会出现偶数情况，所以判断 \(>= 0\) 即可。

    由于中位数必然满足单调性，且满足条件最大的可能也会小于等于数组长度，所以只需在 \([1, n]\) 之间二分即可。

    \(check\)函数：

        根据当前中位数，将数组转换成 \(+-1\) 前缀和。

        由于规定区间长度最少为 k, 那么我们就初始令 \(r = k, l = 0\)，每次循环让 \(r\) 递增，此时 \(l\) 的取值范围为\([0, r – k]\)，每次我们都贪心地选择 \([0, r – k]\) 区间内的最小前缀，这样如果 \(pre[r] >= pre[l]\)，就说明 \(x\) 可以当作数组某个子数组的中位数。

关键代码：

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

    ll ansl, ansr;
    auto check = [&](ll val)
    {
        vector<int> pre(n + 1, 0);
        for (int i = 1; i <= n; ++i)
            pre[i] = pre[i - 1] + (a[i] >= val ? 1 : -1);

        for (int i = k, j = 0; i <= n; ++i)
        {
            if (pre[j] > pre[i - k])
                j = i - k;

            if (pre[i] >= pre[j])
            {
                ansl = j + 1;
                ansr = i;
                return 1;
            }
        }

        return 0;
    };

    int l = 1, r = n;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }

    check(l);

    cout << l << ' ' << ansl << ' ' << ansr << endl;
}

E2. Submedians (Hard Version)

    还没补。