D. Bracket Coloring

链接

---

$题目大意就是给一个括号序列染色以成为漂亮的括号序列$
$题目要求最少染色颜色种类$
$不难发现，只要左括号和右括号数量相等就一定可以成为漂亮的括号序列$
$当左括号右括号数量相等的情况下，我们发现完美的括号子序列就是$
$括号匹配顺序相同的一组括号对，当出现括号匹配顺序不同的时候就是下一个颜色$
$括号匹配顺序相同的意思就是这一子序列都是()()()这样的一左一右，而不出现)(的顺序$
$关于染色，我们就可以先遍历一次字符串，在这个过程中给符合s[0]匹配方式$
$的括号染色为1即全部()()()(())或者全部)()())((的子序列$
然后剩余的括号组成的都是另一种匹配方式，所以顶多还会出现另一种颜色，我们染为2即可

---

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;int t, n;
int res[N];void solve()
{cin >> n;string s;cin >> s;int ll = 0, rr = 0;for(int i = 0; i < n; i ++){if(s[i] == '('){ll ++;}else rr ++;res[i] = 0;}if(ll != rr) {puts("-1");return ;}queue<int> l;char c = s[0];l.push(0);for(int i = 1; i < n; i ++){if(s[i] == c){l.push(i);}else{if(l.size()){res[i] = 1;int tem = l.front();res[tem] = 1;l.pop();}else{res[i] = 2;}}}int cnt = 1;if(l.size()) cnt = 2;while(l.size()){int tem = l.front();res[tem] = 2;l.pop();}printf("%d\n", cnt);for(int i = 0; i < n; i ++){printf("%d ", res[i]);}cout << endl;return ;
}int main()
{cin >> t;while(t --){solve();}return 0;
}/*
)(()(((()))()()(())))((()))))(()(()(())))()()(()(())((()))(())((()
*/

---