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

题意

给你一个仅包含 ( 和 ) 字符串

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

CPP

#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; // 结束 (｡･ω･｡)
}

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

文章操作

题意

思路

Code

相关推荐

评论

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