codeforce每日一题
题目描述
给你一个字符串,请你将其分块,使得每一块都是好的字符串。如果满足以下条件之一,那么方括号序列就称为好的: 它是一个正则的方括号序列;如果这个序列中字符的顺序颠倒,它就变成一个正则的方括号序列。
样例
输入样例1
4
8
((())))(
4
(())
4
))((
3
(()
输出样例1
2
2 2 2 1 2 2 2 1
1
1 1 1 1
1
1 1 1 1
-1
算法
(暴力枚举) $O(n)$
如果n是奇数,直接输出-1.否则判断字符串中$’(‘$,$’)’$数量是否相同,如果不相同,直接输出-1。再判断该字符串反转后是否是正则字符串,如果是,直接输出。如果以上都不是,我们从前向后循环,如果发现前面的$’(‘$严格小于$’)’$,我们就从后面找$’(‘$与前面多的$’)’$匹配。其实我们发现颜色数量不是1就是2.
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
inline void solve()
{
cin>>n;
string str;
cin>>str;
if(n%2) cout<<-1<<endl;
else{
int s = 0;
for(int i=0;i<n;i++)
if(str[i]=='(') s++;
if(s!=n/2){
cout<<-1<<endl;
return;
}
stack<char> stk;
for(int i=0;i<n;i++)
if(stk.size())
{
if(stk.top()=='(' && str[i]=='(') stk.pop();
else{
if(str[i]=='(') stk.push(')');
else stk.push('(');
}
}else{
if(str[i]=='(') stk.push(')');
else stk.push('(');
}
if(!stk.size()){
cout<<1<<endl;
for(int i=0;i<n;i++) cout<<1<<" ";
cout<<endl;
return;
}
s = 0;
vector<bool> st(n, 0);
for(int i=0,j=n-1;i<=j;i++){
if(str[i]=='(') s++;
else s--;
if(s<0){
st[i] = true;
while(j>i && str[j]!='(') j--;
st[j] = true;
j--;s++;
}
}
bool flag = false;
for(int i=1;i<n;i++)
if(st[i]!=st[i-1]){
flag = true;
break;
}
if(flag){
cout<<2<<endl;
for(int i=0;i<n;i++)
if(st[i]) cout<<1<<" ";
else cout<<2<<" ";
cout<<endl;
}else{
cout<<1<<endl;
for(int i=0;i<n;i++) cout<<1<<" ";
cout<<endl;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}