D. Bracket Coloring
链接
题目大意就是给一个括号序列染色以成为漂亮的括号序列 题目大意就是给一个括号序列染色以成为漂亮的括号序列 题目大意就是给一个括号序列染色以成为漂亮的括号序列
题目要求最少染色颜色种类 题目要求最少染色颜色种类 题目要求最少染色颜色种类
不难发现,只要左括号和右括号数量相等就一定可以成为漂亮的括号序列 不难发现,只要左括号和右括号数量相等就一定可以成为漂亮的括号序列 不难发现,只要左括号和右括号数量相等就一定可以成为漂亮的括号序列
当左括号右括号数量相等的情况下,我们发现完美的括号子序列就是 当左括号右括号数量相等的情况下,我们发现完美的括号子序列就是 当左括号右括号数量相等的情况下,我们发现完美的括号子序列就是
括号匹配顺序相同的一组括号对,当出现括号匹配顺序不同的时候就是下一个颜色 括号匹配顺序相同的一组括号对,当出现括号匹配顺序不同的时候就是下一个颜色 括号匹配顺序相同的一组括号对,当出现括号匹配顺序不同的时候就是下一个颜色
括号匹配顺序相同的意思就是这一子序列都是 ( ) ( ) ( ) 这样的一左一右,而不出现 ) ( 的顺序 括号匹配顺序相同的意思就是这一子序列都是()()()这样的一左一右,而不出现)(的顺序 括号匹配顺序相同的意思就是这一子序列都是()()()这样的一左一右,而不出现)(的顺序
关于染色,我们就可以先遍历一次字符串,在这个过程中给符合 s [ 0 ] 匹配方式 关于染色,我们就可以先遍历一次字符串,在这个过程中给符合s[0]匹配方式 关于染色,我们就可以先遍历一次字符串,在这个过程中给符合s[0]匹配方式
的括号染色为 1 即全部 ( ) ( ) ( ) ( ( ) ) 或者全部 ) ( ) ( ) ) ( ( 的子序列 的括号染色为1即全部()()()(())或者全部)()())((的子序列 的括号染色为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;
}/*
)(()(((()))()()(())))((()))))(()(()(())))()()(()(())((()))(())((()
*/