2022 年牛客多校加赛场 G 题题解

G Good red-string

题意：给定一个长度为 $nn$ 的串，仅由 r，e，d，?构成。问能够找到一种将全部的 ?转化为 r，e，d中的一种字符，使得最后的串由 ${\displaystyle \frac{n}{3}}\backslash dfrac\{n\}\{3\}$ 个不相交的 red子序列构成。例如 reredd符合条件而 rederd不符合条件。保证 $nn$ 为三的倍数，$n\le 3\times 10^{5}n\; \backslash leq\; 3\backslash times\; 10^5$。

解法：考虑对 e的约束条件：每一个 d前必须至少有一个 e；每一个 r后面至少有一个 e。因而仅针对这两条关系，可以用栈去安排出刚需的问号转化方法。对于剩下的问号，则从左到右的尽可能安排 red即可。最后检查一下是否符合条件即可。

这样做的正确性在于，所有的约束关系都集中到 e这里，也就是在单独对 r贪心的时候，也是符合 d的贪心要求的。

#include <bits/stdc++.h>
using namespace std;
bool solve(string &str)
{
    int r = 0, e = 0, d = 0, n = str.length();
    stack<int> s;
    for (int i = 0; i < n; i++)
    {
        if (str[i] == 'e')
            e++;
        else if (str[i] == 'd')
        {
            if (e)
                e--;
            else if (!s.empty())
            {
                str[s.top()] = 'e';
                s.pop();
            }
            else
                return false;
        }
        else if (str[i] == '?')
            s.push(i);
    }
    while (!s.empty())
        s.pop();
    e = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        if (str[i] == 'e')
            e++;
        else if (str[i] == 'r')
        {
            if (e)
                e--;
            else if (!s.empty())
            {
                str[s.top()] = 'e';
                s.pop();
            }
            else
                return false;
        }
        else if (str[i] == '?')
            s.push(i);
    }
    e = 0;
    for (auto i : str)
        if (i == 'r')
            r++;
        else if (i == 'e')
            e++;
        else if (i == 'd')
            d++;
    for (int i = 0; i < n; i++)
        if (str[i] == '?')
        {
            if (3 * r < n)
            {
                str[i] = 'r';
                r++;
            }
            else if (3 * e < n)
            {
                str[i] = 'e';
                e++;
            }
            else if (3 * d < n)
            {
                str[i] = 'd';
                d++;
            }
        }
    r = e = d = 0;
    for (auto i : str)
    {
        if (i == 'r')
            r++;
        if (i == 'e')
            e++;
        if (i == 'd')
            d++;
        if (r < e || e < d)
            return false;
    }
    if (r != e || e != d)
        return false;
    else
        return true;
}
int main()
{
    string s;
    int t;
    scanf("%d", &t);
    while (t--)
    {
        cin >> s;
        if (solve(s))
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}