题面过长,就不放了
题目解析
这道题需要仔细读题 审题很重要。
读完题后,第一反应是括号匹配(本人掉入此坑浪费了大量时间),但是仔细读题后,你会发现事情不是那么简单(其实是你想复杂了)。
本题需要注意两点:
?
可以任意替换成(
或者)
- 测试数据中只会出现一对括号
弄明白这两点之后,其实本题的难度就大大下降了。既然?
可以替换成 (
和 )
,那么在大多数情况下,一串字符是可以构成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; }