CF 1709C Recover an RBS

標籤： cf

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

设 $dep$ 表示括号序列的栈大小，遇到 ”(” 则 $dep + 1$，遇到 ”)” 则 $dep - 1$，所谓的正确括号序列则是在任意时刻 $dep \ge 0$ 且最后 $dep = 0$。

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

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");
}