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

A. Incremental Subarray

算法：

    贪心。

思路：

    不难发现以下规律：

• 一个单调上升的子数组在数组中出现次数的取决于最后一个元素。
• 如果一个子数组存在下降，那么其答案必然为 \(1\)。

关键代码：

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

    if (m == 1)
    {
        cout << n - a[1] + 1 << endl;
        return;
    }

    ll ans = n - a[1] + 1;
    for (int i = 2; i <= m; ++i)
    {
        if (a[i] <= a[i - 1])
            ans = 1;
        else
            ans = n - a[i] + 1;

        if (ans == 1)
        {
            cout << 1 << endl;
            return;
        }
    }

    cout << ans << endl;
}

B. Incremental Path

算法：

    贪心，找规律。

思路：

    玩几组样例后不难想到，第 \(i\) 人和第 \(i + 1\) 人的前 \(i – 1\) 步操作是一样的，那么只需线性遍历即可。

    对于第 \(i\) 步操作：

• 如果为 \(B\)，下一个人的前 \(i\) 步操作必然到达第 \(i\) 人到达的位置的后面。
• 如果为 \(A\)，下一个人的前 \(i\) 步操作必然和第 \(i\) 人到达的位置相同。

关键代码：

void miyan()
{
    int n, m;
    string s;
    cin >> n >> m >> s;
    set<int> a;
    for (int i = 0; i < m; ++i)
    {
        int x;
        cin >> x;
        a.insert(x);
    }

    ll now = 1;
    for (int i = 0; i < n; ++i)
    {
        ++now;
        if (s[i] == 'B')
        {
            while (a.count(now))
                ++now;
        }

        a.insert(now);

        if (s[i] == 'B')
        {
            while (a.count(now))
                ++now;
        }
    }

    cout << a.size() << endl;
    for (auto x : a)
        cout << x << ' ';
    cout << endl;
}

C. Incremental Stay

算法：

    贪心，前缀和。

思路：

    贪心策略：

        通过最多容纳 \(k\) 个人，可以想到可以让前 \(k – 1\) 人留到最后，中间的人进来紧接着就出去，这样就最大化了差值，由于要 \(k\) 要对于 \(1\) 到 \(n\) 都输出，使用前缀和优化一下即可。

关键代码：

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

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

        if (i & 1)
        {
            ll pos = (i + 1) / 2;
            s1[pos] = s1[pos - 1] + a[i];
        }
        else
        {
            ll pos = i / 2;
            s2[pos] = s2[pos - 1] + a[i];
        }
    }

    ll l = 0, r = n;
    ll L = 1, R = n;
    for (int k = 1; k <= n; ++k)
    {
        ll ans = 0;
        ll t = k - 1;
        ans += s[n + n] - s[n + n - t] - s[t];

        if (t & 1)
            ans += s1[R] - s1[L] - s2[R-- - 1] + s2[L++ - 1];
        else
            ans += s2[r] - s2[l] - s1[r--] + s1[l++];

        cout << ans << ' ';
    }
    cout << endl;
}

D. Grid Counting

    组合数学以后再补。