题目传送门

题面过长,就不放了

题目解析

这道题需要仔细读题 审题很重要

读完题后,第一反应是括号匹配(本人掉入此坑浪费了大量时间),但是仔细读题后,你会发现事情不是那么简单(其实是你想复杂了)。

本题需要注意两点:

  1. ?可以任意替换成 (或者 )
  2. 测试数据中只会出现一对括号

弄明白这两点之后,其实本题的难度就大大下降了。既然可以替换成 () ,那么在大多数情况下,一串字符是可以构成RBS的。所以可以试着采用贪心策略,分析一下哪些情况无法构成RBS。首先,为了保证括号互相匹配,就得保证字符串的长度为偶数,那么当字符串的长度为奇数时,必定无法构成RBS;其次,如果开头为)或结尾为(,则必定无法构成RBS。所以,当字符串长度为奇数,如果开头为)或结尾为(,则必定无法构成RBS,其余情况下都能构成。

AC代码

#include<iostream>
using namespace std;
int main(){
    int t;
    cin >> t;
    while(t--){
        string s;
        cin >> s;
        int len = s.length();
        if(s[0] == ')' || s[len - 1] == '(' || len ^ 1)
            cout << "NO" << endl;
        else cout << "YES" << endl;
    }

    return 0;
}