CF 1709C Recover an RBS

标签: cf

给定一个由 ”?”,”(”,”)” 组成的字符串,”?” 可以替换成 ”(” 或 ”)“,问是否有仅有一种方法使得字符串是正确的括号序列。

表示括号序列的栈大小,遇到 ”(” 则 ,遇到 ”)” 则 ,所谓的正确括号序列则是在任意时刻 且最后

首先考虑将原字符串还原成一个括号序列。由于要满足 因此优先填 ”(“。然后考虑将其转成不同的括号序列,在 ”(” 与 ”)” 交界的地方交换,保证这个交换对栈的大小的影响最小。

bool check(const std::string &s)
{
    int dep = 0;
    for (auto i : s)
    {
        if (i == '(') dep++;
        if (i == ')') dep--;
        if (dep < 0) return false;
    }
    return dep == 0;
}

void solve()
{
    std::string s;
    std::cin >> s;
    int n = s.size();
    std::vector<int> pos;
    int lcnt = n / 2, rcnt = n / 2;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == '?') pos.emplace_back(i);
        if (s[i] == '(') lcnt--;
        if (s[i] == ')') rcnt--;
    }
    if (lcnt == 0 || rcnt == 0)
    {
        puts("Yes");
        return ;
    }

    int tmp = -1;
    for (int i = 0, __end = pos.size(); i < __end; i++)
    {
        if (i < lcnt) s[pos[i]] = '(';
        else
        {
            s[pos[i]] = ')';
            if (tmp == -1) tmp = i;
        }
    }
    std::swap(s[pos[tmp]], s[pos[tmp - 1]]);
    if (check(s)) puts("No");
    else puts("Yes");
}