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;
}