题解：P14172 【MX-X23-T2】括号串

UNNN · 2025-10-06 20:23:35 · 题解

题意

给你一个仅包含 ( 和 ) 字符串 s，如果这个字符串的括号能够两两配对或者可以通过 仅修改一对 )(至 () 使得括号两两配对则称这个字符串合法。问你 s 合不合法。

思路

看题发现 s 仅包含小括号不包含中括号大括号，所以检测括号匹配只需要一个变量 cnt 来计数即可。

如果遍历到 (，则 cnt++；如果遍历到 )，则 cnt--。若最终 cnt 的值变为 0，则括号能够两两匹配，直接输出 Yes。

题目还说可以进行一次操作使得 s 中的 )( 变为 ()。一般情况下，如果括号能够正常匹配，则无需进行这一步操作，遍历过程中 cnt 的值不会小于 0。但如果出现 ) 过剩的情况，cnt 的值就有可能为负了。此时就需要检测这个 ) 是否能和下一个字符构成一个 )(，如果可以，那么交换这两个字符，同时由于之前这个字符为 ) 会导致 cnt 减 1，变回来后 cnt 就要把这个 1 加回来，同时因为这个字符变成了 ( 所以还要加 1，因此 cnt 的值需要加 2。

如果不能构成 )( 或者出现了多于一处 )( 的话，那么循环终止，直接输出 No。

最后如果 cnt 的值能够归 0 则输出 Yes，否则输出 No。

Code

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
const int MAXN = 1e5 + 5;
int t, n;
string s;
int cnt = 0;
bool flag = false;
int main()
{
    scanf("%d", &t);
    while(t--){
        cnt = 0;
        flag = true; // 记录是否有多处 )(
        scanf("%d", &n);
        cin >> s;
        for(int i = 0;i < s.length();i++){
            if(s[i] == '(') cnt++; // 左括号
            else if(s[i] == ')') cnt--; // 右括号
            if(cnt < 0){
                // 出现多余的 )
                if(s[i + 1] == '(' && !flag){
                    swap(s[i], s[i + 1]); // 将 )( 改为 ()
                    cnt = cnt + 2; // 加 2 原因见上
                    flag = true; // 进行了一次操作
                }
                else break; // 字符串不合法，直接停止遍历
            }
        }
        if(cnt != 0) puts("No");
        else puts("Yes");
    }
    return 0; // 结束 (｡･ω･｡)
}