CF1860A 讲解
CF1860A 讲解
题目大意
共有 \(t\) 组数据，每组数据给你一个字符串 \(s\)，每个字符串 \(s\) 都是由 ( 和/或 ) 组成的。
问能否找到一个合法的字符串 \(s'\)，使得：
-
\(\left| s' \right| = 2 \times \left| s \right|\)，即字符串 \(s'\) 的长度为字符串 \(s\) 长度的二倍。
-
字符串 \(s\) 不是字符串 \(s'\) 的子串，即 \(s'\) 中不存在 \(s\)。
-
字符串 \(s'\) 是一个正则括号序列，即括号的排列是合理的（也就是保证左括号的数量要时刻大于等于右括号的数量）。
如果能找到这样一个字符串 \(s'\)，就输出 YES 并输出该字符串。否则输出 NO。
简要思路
我们考虑字符串 \(s\) 可能出现的情况：
-
字符串 \(s\) 包含两个连续相等的字符，比如：
((),))((。在这种情况下，我们可以构造一个没有两个连续相等的字符的字符串 \(s'\)，即形如（）（）（）的形式的字符串。 -
字符串 \(s\) 不包含两个连续相等的字符，也就是说所有相邻的字符都是不一样的（即交替的），比如：
()(,)(,()。在这种情况下，我们需要构造出一个不交替的字符串来实现答案，但是我们无法构造出一个完全没有交替字符的合法的字符串，只能构造出形如((()))的字符串。在这里，最长的交替子串的长度为 \(2\)。
因此，我们只需要考虑两种形式的字符串中是否包含 \(s\) 即可。
完整代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int t;
signed main(){
cin>>t;
while(t--){
string s;
cin>>s;
int len=s.length();
string a,b;
for(int i=0;i<2*len;i++){
if(i%2==0)a+="(";
else a+=")";//构造形如 ()() 的字符串
if(i<len)b+="(";
else b+=")";//构造形如 (()) 的字符串
}
if(a.find(s)==string::npos){//如果在 a 中没有出现 s 这个字符串就会返回 npos
cout<<"YES"<<endl;
cout<<a<<endl;
}
else if(b.find(s)==string::npos){
cout<<"YES"<<endl;
cout<<b<<endl;
}
else cout<<"NO"<<endl;//没有构造的字符串中不含有 s
}
return 0;
}