链接：https://ac.nowcoder.com/acm/contest/127703

A – ICPC Balloons

算法：

模拟。

思路：

无。

关键代码：

void miyan()
{
    char c;
    cin >> c;

    if (c == 'A')
        cout << "red" << endl;
    else if (c == 'B')
        cout << "orange" << endl;
    else if (c == 'C')
        cout << "blue" << endl;
    else
        cout << "green" << endl;
}

B – String Covering

算法：

贪心。

思路：

结论：单个 \(1\) 是染不出来的。

关键代码：

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

    int cnt = 0;
    for (auto c : s)
    {
        if (c == '1')
            ++cnt;

        if (c == '0')
        {
            if (cnt && cnt == 1)
            {
                cout << "NO" << endl;
                return;
            }

            cnt = 0;
        }
    }

    if (cnt && cnt == 1)
    {
        cout << "NO" << endl;
        return;
    }

    cout << "YES" << endl;
}

C – Get The Sequence

算法：

贪心，双指针。

思路：

贪心双指针匹配即可。

既，定义 \(i = 0\)（指向数组 \(a\) 的第一个元素），\(j = 0\)（指向数组 \(b\) 的第一个元素）：

• 如果 \(a[i] \ge b[j]\)，代表 \(a[i]\) 可与 \(b[j]\) 进行匹配且 \(a[i]\) 是当前首个满足条件的，执行 \(i := i + 1, j := j + 1\)；
• 否则，当前 \(a[i]\) 不可与 \(b[j]\) 匹配，单独移动 \(i\) 指针，既 \(i := i + 1\)。
• 最终判断 \(j\) 是否等于 \(m\) 即可。

关键代码：

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

    int i = 0, j = 0;
    while (i < n && j < m)
    {
        if (a[i] >= b[j])
            ++j;

        ++i;
    }

    if (j == m)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

D – Longest Subsequence

算法：

\(dp\)。

思路：

简单 \(dp\)。

定义 \(dp(x)\) 为以 \(x\) 结尾的最长子序列长度。

易得状态转移：\(dp(x) = max(1, dp(x), dp(x – 1) + 1, dp(x + 1) + 1)\)。

最终答案为最大的 \(dp\) 值。

关键代码：

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

    vector<int> dp(n + 2, 0);
    for (int i = 0; i < n; ++i)
        dp[a[i]] = max({1, dp[a[i]], dp[a[i] - 1] + 1, dp[a[i] + 1] + 1});

    cout << ranges::max(dp) << endl;
}

E – Eat The Candy

算法：

前后缀优化。

思路：

经典前后缀优化题目。

定义：

• \(pre(i)\) 为吃掉 \([1, i]\) 所有糖果可以得到的额外糖果数量；
• \(suf(i)\) 为吃掉 \([i, n]\) 所有糖果可以得到的额外糖果数量。

\(pre\) 和 \(suf\) 可以在 \(O(n)\) 的时间内预处理得到。

那么对于每个 \(i\)，都将额外的糖果放到 \(i\) 中，其最终糖果个数为 \(a[i] + pre(i – 1) + suf(i + 1)\)，答案取全局最大即可。

关键代码：

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

    auto b = a;

    vector<ll> pre(n + 2, 0);
    vector<ll> suf(n + 2, 0);
    for (int i = 1; i <= n; ++i)
    {
        pre[i] = pre[i - 1];

        ll t = min(b[i], b[i - 1]);
        pre[i] += t;
        b[i] -= t;
    }

    b = a;

    for (int i = n; i >= 1; --i)
    {
        suf[i] = suf[i + 1];

        ll t = min(b[i], b[i + 1]);
        suf[i] += t;
        b[i] -= t;
    }

    ll ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        ll cur = a[i] + pre[i - 1] + suf[i + 1];

        ans = max(ans, cur);
    }

    cout << ans << endl;
}

F – Bracket Coloring

算法：

栈，并查集，括号序列。

思路：

容易想到在一个匹配的括号序列分量中，其只有两种染色方法，读者易自证。

使用栈对括号序列进行匹配，然后对分量维护并查集，最终答案就为 \(2^{分量个数}\)。

具体实现看代码。

关键代码：

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

    s = ' ' + s;

    vector<int> p(n + 10);
    for (int i = 1; i <= n; ++i)
        p[i] = i;

    auto find = [&](auto &&self, int x) -> int
    {
        if (x != p[x])
            p[x] = self(self, p[x]);

        return p[x];
    };

    vector<pair<char, int>> stk;
    for (int i = 1; i <= n; ++i)
    {
        if (i > 1 && s[i] == s[i - 1])
        {
            int fa = i, fb = i - 1;

            fa = find(find, fa);
            fb = find(find, fb);

            if (fa != fb)
                p[fa] = fb;
        }

        if (s[i] == '(')
            stk.push_back({s[i], i});
        else
        {
            auto [c, pos] = stk.back();
            stk.pop_back();

            int fa = i, fb = pos;
            fa = find(find, fa);
            fb = find(find, fb);

            if (fa != fb)
                p[fa] = fb;
        }
    }

    ll ans = 1;
    for (int i = 1; i <= n; ++i)
        if (find(find, i) == i)
            ans = ans * 2ll % MOD;

    cout << ans << endl;
}