CF1709C Recover an RBS

happybob · 2022-07-24 12:51:04 · 题解

题意

共 t 组数据，每组给定一个字符串 s，包括 (， ) 和 ?。你可以进行无限次操作，每次把一个 ? 换成一个 ( 或者一个 )。问是否有多种方法可以将这个字符串变为一个正确的括号序列。

解法

考虑贪心。

对于每一个字符串，我们不妨先找到其中一个正确的括号序列。假设最初这个字符串长度为 n，其中有 x 个 (，y 个 )。那么我们要将 \dfrac{n}{2} - x 个 ? 替换成 (，把 \dfrac{n}{2} - y 个 ? 替换成 )。

显然当一个字符串是一个括号序列时，对于每一位 i，从 1 到 i 中 ( 的出现次数一定 \geq ) 出现的次数。并且最终 ( 和 ) 出现次数一样。

我们不妨找到 ? 变成 ( 的所有字符中最靠后的一个和 ? 变成 ) 最靠前的一个。交换这两个 ( 和 )。如果交换后这是一个合法括号序列，那么至少有两种合法方案，如果不合法，则只有一种合法方案。

接下来考虑证明：

假设找到的两个位置为 i 和 j。反证，如果有另一个合法序列，交换了 x 和 y，显然不存在 x > i 或 y < j，因为 i 和 j 都是端点。那么一定有 x \leq i 和 y \geq j。显然对于 1 到 x - 1 和 y + 1 到 n 而言，与交换 i, j 没有区别对于中间的括号，由于 x 和 y 的范围比 i 和 j 大，显然选取较小的范围也一定可以。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;

int t;
string s;

inline bool check(string p)
{
    int c1 = 0, c2 = 0, l = p.size() - 1;
    for (int i = 0; i <= l; i++)
    {
        c1 += p[i] == '(';
        c2 += p[i] == ')';
        if (c1 < c2) return 0;
    }
    if (c1 != c2) return 0;
    return 1;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> t;
    while (t--)
    {
        cin >> s;
        int l = s.size() - 1;
        int c1 = count(s.begin(), s.end(), '('), c2 = count(s.begin(), s.end(), ')');
        string copy = s;
        int pl = 0, pr = 0;
        for (int i = 0; i <= l; i++)
        {
            if (copy[i] == '?' && c1 + 1 <= (l + 1) / 2) copy[i] = '(', c1++, pl = i;
            else if (copy[i] == '?')
            {
                copy[i] = ')', c2++;
                if (!pr) pr = i;
            }
        }
        string h = copy;
        swap(copy[pl], copy[pr]);
        if (h != copy && check(copy))
        {
            printf("NO\n");
        }
        else printf("YES\n");
    }
    return 0;
}