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

A. Array Coloring

算法：

模拟。

思路：

两种情况（\(0\) 开头，\(1\) 开头），都试一遍。

关键代码：

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

    auto check = [&](int start) -> bool
    {
        vector<int> st(n + 1, 0);
        for (int i = 0; i < n; ++i)
        {
            st[a[i]] = start;
            start = !start;
        }

        vector<int> b = a;
        ranges::sort(b);
        for (int i = 1; i < n; ++i)
            if (st[b[i]] == st[b[i - 1]])
                return 0;

        return 1;
    };

    if (check(1) || check(0))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

B. MEX Reordering

算法：

贪心。

思路：

• 容易想到，不存在 \(0\) 的时候，不管怎么重排前缀和后缀的 \(mex\) 都为 \(0\)；
• 当存在一个 \(0\) 的时候，把其放到最后面可满足任意前缀后缀都不相等；
• 当存在两个及以上 \(0\) 的时候，需要有个 \(1\) 来配平。

关键代码：

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

    map<int, int> m;
    for (auto x : a)
        ++m[x];

    if (!m.count(0))
        cout << "NO" << endl;
    else if (m[0] >= 2 && !m.count(1))
        cout << "NO" << endl;
    else
        cout << "YES" << endl;
}

C. Sorting Game

算法：

贪心，博弈论。

思路：

通过样例不难想到当字符串是有序的时候，\(Alice\) 无法操作，\(Bob\) 胜利。

剩余情况是 \(Alice\) 胜利。

证明：

• 最终无法操作的字符串是有两段构成的，既 \(n\) 个 \(0\)，\(m\) 个 \(1\)，\(Alice\) 只需要在首次操作中选择不在正确位置的字符即可，因为如果有 \(k (k < min(n, m))\) 个 \(0\) 在 \(1\) 的位置，那么必然有 \(k\) 个 \(1\) 在 \(0\) 的位置。

关键代码：

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

    string ss = s;
    ranges::sort(ss);
    if (s == ss)
    {
        cout << "Bob" << endl;
        return;
    }

    cout << "Alice" << endl;

    vector<int> ans;
    for (int i = 0; i < n; ++i)
        if (s[i] != ss[i])
            ans.push_back(i + 1);

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

D1. Sub-RBS (Easy Version)

算法：

贪心。

思路：

因为是从 \(s\) 中选一个子序列 \(t\) 且 \(t != s\)，因此第一个条件直接不用考虑。

将问题转换为删除尽可能少的字符，使 \(t\) 是正则括号序列且 \(t\) 优于 \(s\)。

要想让 \(t\) 优于 \(s\)，需要 \(t[i] = ‘(‘\) 并且 \(s[i] = ‘)’\) 且 \(equals_{j = 1}^{i – 1} t[j] = s[j]\)。

找到 \(“)(”\)，删除其中的 \(‘)’\)，并在 \(“)(”\) 后面找到一个 \(‘(’\) 将其删除。

为什么正确？

• 括号序列满足的条件是前缀中左括号的个数永远大于等于右括号的个数，且整个序列的左右括号数量相等，不难想到在删除 \(‘)’\) 和 \(‘(’\) 后，整个序列还是满足的。

关键代码：

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

    for (int i = 0; i < n - 1; ++i)
    {
        if (s[i] == ')' && s[i + 1] == '(')
        {
            int cnt = 0;
            for (int j = i + 2; j < n; ++j)
                cnt += s[j] == '(';

            if (cnt)
            {
                cout << n - 2 << endl;
                return;
            }
            else
                break;
        }
    }

    cout << -1 << endl;
}

D2. Sub-RBS (Hard Version)

还没补。