Bicolored RBS 题解

模拟两个颜色的扩号层数, 贪心, 如果是左括号, 哪边的层数浅就放那边; 如果是右括号, 哪边的层数深就放那边.

至于层数的维护, 两个 int 就做掉了

放个代码:

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
inline int read(){
    int x = 0; int zf = 1; char ch = ' ';
    while (ch != '-' && (ch <'0' || ch> '9')) ch = getchar();
    if (ch == '-') zf = -1, ch = getchar();
    while (ch>= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;
}
int rd = 0;
int bl = 0;
int ans[200005];
int main(){
    int n = read();
    string s; cin>> s;
    for (int i = 0; i <n; ++i){
        if (s[i] == ')')
            (rd> bl) ? (--rd, ans[i] = 0) : (--bl, ans[i] = 1);
        else if (s[i] == '(')
            (rd < bl) ? (++rd, ans[i] = 0) : (++bl, ans[i] = 1);
    }
    for (int i = 0; i < n; ++i)
        printf("%d", ans[i]);
    return 0;
}

[CF1167D]Bicolored RBS 题解

来源: http://www.bubuko.com/infodetail-3064044.html