CF Edu 65 D

cxccxc · 2019-07-25 13:50:09 · 个人记录

为了使括号深度最小，两种颜色的深度分别为a和b，a+b=n，则min{max(a,b)}=n/2，此时a=b

由此得出可以以红蓝相间的方式染色

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#define INF 1<<30
#define LL long long
#define ULL unsigned long long
#define MAXN 200005
using namespace std;
int n;
string s; 
int a[MAXN];
int main()
{
    cin>>n>>s;
    int o=1,c=1;
    for(int i=0;i<n;i++){
        if(s[i]=='('){
            a[i]=o;
            o=1-o;
        }
        if(s[i]==')'){
            a[i]=c;
            c=1-c;
        }
        printf("%d",a[i]);
    }
    return 0;
}