Educational Codeforces Round 65 (Rated for Div. 2) D. Bicolored RBS

传送门

 

参考资料：

　　[1]:https://www.cnblogs.com/wangrunhu/p/10880130.html

　　[2]:https://blog.csdn.net/weixin_43262291/article/details/90271693

题意（摘抄自[1]）：

　　给定一个RBS串(括号匹配的)，问你怎么把它分解成两个RBS串，使得他们的最大嵌套深度最小。

　　

题解（摘抄自[1]）：

　　对于给定的RBS串，我们先遍历一遍求出最大的嵌套深度maxDep。

　　那么maxDep / 2 一定是满足题意的最小的的最大嵌套深度。

　　在遍历一遍RBS串：

　　①若为 '(' 且个数 < maxDep / 2 ，那么将该位置标记为0；

　　②若为 '(' 但个数 ≥ maxDep / 2 ，则标记为1；

　　对于 ')’ 只要将其标记为与他对应的 '(' 的数字即可。

　　（这里0，1互换也可以）

AC代码（换成了我的风格，不喜勿喷，还望大佬见谅）：

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+50;

int n;
char s[maxn];
stack<int >sta;
int ans[maxn];

void Solve()
{
    while(!sta.empty())
        sta.pop();

    int maxDep=0;
    for(int i=1;i <= n;++i)
    {
        if(s[i] == '(')
            sta.push(i);
        else
            sta.pop();
        maxDep=max(maxDep,(int)sta.size());
    }
    while(!sta.empty())
        sta.pop();

    maxDep >>= 1;
    for(int i=1;i <= n;++i)
    {
        if(s[i] == '(')
        {
            if(sta.size() < maxDep)
            {
                sta.push(0);
                ans[i]=0;
            }
            else
            {
                sta.push(1);
                ans[i]=1;
            }
        }
        else
        {
            ans[i]=sta.top();
            sta.pop();
        }
    }
    for(int i=1;i <= n;++i)
        printf("%d",ans[i]);
    printf("\n");
}
int main()
{
    scanf("%d%s",&n,s+1);
    Solve();

    return 0;
}

 

看了这篇博文后，[2]的思路瞬间理解了；

0,1互换着穿插，连续的 '(' 被分成了原来的 1/2；（tql）

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=5e5+50;

int n;
char s[maxn];
int ans[maxn];

void Solve()
{
    int a=0;
    int b=0;
    for(int i=0;i < n;++i)
    {
        if(s[i] == '(')
            ans[i]=a,a=!a;
        else 
            ans[i]=b,b=!b;
        
        printf("%d",ans[i]);
    }
    printf("\n");
}
int main()
{
    scanf("%d",&n);
    scanf("%s",s);
    Solve();

    return 0;
}