Recover an RBS

Created by LXC on Fri Apr 5 03:07:23 2024

https://codeforces.com/problemset/problem/1709/C

ranting: 1800

tag: constructive algorithms, greedy, implementation, strings

problem

有个合法括号序列，部分字符被 ? 替换了，问是否存在唯一的一种填 ? 的方案，使得括号序列合法，即判断填 ? 使得括号序列合法的方案数是否等于1。存在唯一方案输出 YES，方案不唯一输出 NO

序列长度 $\sum n\le 2\times 10^5$，测试点数 $T\leq 5\times 10^4$

第一行输出测试点总数 $T$。

之后每一行一个字符串 $s$ 表示替换掉部分字符后的合法括号序列。

solution

如果问号被替换后串是唯一的，那么这个串我们是可以构造出来的。

我们知道如果串的长度是n，那么必有n为偶数，且有n/2个左括号和n/2个右括号

现在我们可以统计出现有的左右括号数，然后计算还需要的左右括号数。

将需要的左括号尽可能放在左边，将需要的右括号尽可能放在右边，而如果将其中一个左括号和右括号进行交换后，发现串仍然合法那么答案就是NO

我们只需要选择问号替换的括号中，最右侧左括号和最左侧右括号进行交换，然后检测是否合法即可。

证明一下

设问号替换的括号中，最右侧左括号位置为x，最左侧右括号位置为y。

我们构造一个序列，对于左括号视为1，右括号视为-1，然后对这个序列求前缀和序列，前缀和序列中必定不能出现负数，否则就是非法序列

如果我们交换了x和y的字符。原本x对后续位置的贡献是1，变为了-1，所以在前缀和序列中x及之后的数都会-2；原本y对后续位置的贡献是-1，变为了1，所以在前缀和序列中x及之后的数都会+2；

因此，只需检测前缀和序列中，x到y的左闭右开区间，存在小于2的数可以断定交换后是不合法的，构造是不唯一的。一旦不合法，对于x左侧的位置和y右侧的位置交换也是不合法的，因为他们也包含了[x,y)这段区间。而一旦合法，则可以证明构造是唯一的。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    string s;
    cin >> s;
    int n = s.size();
    int l = 0, r = 0, q = 0;
    for (auto i:s) {
        if (i == '(') l++;
        if (i == ')') r++;
        if (i == '?') q++;
    }
    int nl = n/2-l, nr = n/2-r;
    if (q < 2 || nl == 0 || nr == 0) {
        cout << "YES\n";
        return ;
    }
    for (int i=0,j=1; j<=nl&&i<n; i++) {
        if (s[i] == '?') {
            if (j == nl) s[i] = ')';
            else s[i] = '(';
            j++;
        }
    }
    for (int i=n-1,j=1; j<=nr&&i>=0; i--) {
        if (s[i] == '?') {
            if (j == nr) s[i] = '(';
            else s[i] = ')';
            j++;
        }
    }
    int c = 0;
    for (int i=0; i<n; i++) {
        if (s[i] == '(') c++;
        else c--;
        if (c < 0) {
            cout << "YES\n";
            return ;
        }
    }
    cout << "NO\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}