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

A. Dr. TC

算法：

    模拟。

思路：

    无。

关键代码：

void solve()
{
    int n;
    string s;
    cin >> n >> s;

    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        if (s[i] == '0')
            ++ans;
        else
            --ans;

        for (int j = 0; j < n; ++j)
            ans += (s[j] == '1') ? 1 : 0;
    }

    cout << ans << endl;
}

B. St. Chroma

算法：

    构造，贪心。

思路：

    先构造出 \(x\) 之前的数字，然后构造 \(x\) 之后的数字，最后根据情况构造 \(x\) 。

关键代码：

void solve()
{
    ll n, x;
    cin >> n >> x;

    vector<int> ans;

    for (int i = 0; i < min(x, n); ++i)
        ans.push_back(i);

    for (int i = min(x, n) + 1; i < max(x, n); ++i)
        ans.push_back(i);

    if (x < n)
        ans.push_back(x);

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

C. Cherry Bomb

算法：

    贪心，模拟。

思路：

    无。

关键代码：

void solve()
{
    int n, k;
    cin >> n >> k;

    vi a(n + 10), b(n + 10);
    cin >> a >> b;

    ll cnt = 0;
    ll val = -1;
    map<ll, ll> m;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] == -1 || b[i] == -1)
            continue;

        ll sum = a[i] + b[i];

        if (!m.count(sum))
            ++cnt, ++m[sum], val = sum;
    }

    if (cnt > 1)
    {
        cout << 0 << endl;
        return;
    }

    ll cntb = count(b.begin(), b.begin() + n, -1);

    if (cntb == n)
    {
        ll minn = MAX, maxx = MIN;
        for (int i = 0; i < n; ++i)
        {
            minn = min(minn, 1ll * a[i]);
            maxx = max(maxx, 1ll * a[i]);
        }

        cout << minn + k - maxx + 1 << endl;
    }
    else
    {
        for (int i = 0; i < n; ++i)
        {
            if ((a[i] != -1 && a[i] > val) || (b[i] != -1 && b[i] > val))
            {
                cout << 0 << endl;
                return;
            }
            if ((a[i] == -1 && b[i] + k < val) || (b[i] == -1 && a[i] + k < val))
            {
                cout << 0 << endl;
                return;
            }
        }

        cout << 1 << endl;
    }
}

D. Flower Boy

算法：

    贪心。

思路：

    定义：

• \(pre[i]\)：\(b\) 中第 \(i\) 朵花在 \(a\) 数组中能插入的最小合法位置（左边界）；既从左往右遍历 \(a\)，找到第一个满足 \(a[j] ≥ b[i]\)的位置。
• \(suf[i]\)：\(b\) 中第 \(i\) 朵花在 \(a\) 数组中能插入的最大合法位置（左边界）；既从右往左遍历 \(a\)，找到第一个满足 \(a[j] ≥ b[i]\)的位置。

    现在我们知道了每朵花的可种植范围了，就遍历数组 \(b\) ，尝试种植 \(b[i]\)， 然后判断一下前后的花朵是不是都可采摘到即可，既对于每个 \(b[i]\)，如果满足 \(pre[i – 1] < suf[i + 1]\)，就说明可以种植 \(b[i]\)。

关键代码：

void solve()
{
    int n, m;
    cin >> n >> m;

    vector<int> a(n + 10), b(m + 10);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= m; ++i)
        cin >> b[i];

    vector<int> pre(m + 10, 0);
    for (int i = 1, j = 1; i <= m; ++i)
    {
        while (j <= n && a[j] < b[i])
            ++j;
        pre[i] = j++;
    }

    if (pre[m] <= n)
    {
        cout << 0 << endl;
        return;
    }

    vector<int> suf(m + 10);
    suf[m + 1] = n + 1;
    for (int i = m, j = n; i >= 0; --i)
    {
        while (j >= 1 && a[j] < b[i])
            --j;
        suf[i] = j--;
    }

    ll ans = MAX;
    for (int i = 1; i <= m; ++i)
        if (pre[i - 1] < suf[i + 1])
            ans = min(ans, 1ll * b[i]);

    if (ans == MAX)
        cout << -1 << endl;
    else
        cout << ans << endl;
}

E. Wolf

    还没补。