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

时间:2023-02-04 19:34:39

传送门

 

参考资料:

  [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代码(换成了我的风格,不喜勿喷,还望大佬见谅):

Educational Codeforces Round 65 (Rated for Div. 2) D. Bicolored RBSEducational Codeforces Round 65 (Rated for Div. 2) D. Bicolored RBS
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=2e5+50;
 4 
 5 int n;
 6 char s[maxn];
 7 stack<int >sta;
 8 int ans[maxn];
 9 
10 void Solve()
11 {
12     while(!sta.empty())
13         sta.pop();
14 
15     int maxDep=0;
16     for(int i=1;i <= n;++i)
17     {
18         if(s[i] == '(')
19             sta.push(i);
20         else
21             sta.pop();
22         maxDep=max(maxDep,(int)sta.size());
23     }
24     while(!sta.empty())
25         sta.pop();
26 
27     maxDep >>= 1;
28     for(int i=1;i <= n;++i)
29     {
30         if(s[i] == '(')
31         {
32             if(sta.size() < maxDep)
33             {
34                 sta.push(0);
35                 ans[i]=0;
36             }
37             else
38             {
39                 sta.push(1);
40                 ans[i]=1;
41             }
42         }
43         else
44         {
45             ans[i]=sta.top();
46             sta.pop();
47         }
48     }
49     for(int i=1;i <= n;++i)
50         printf("%d",ans[i]);
51     printf("\n");
52 }
53 int main()
54 {
55     scanf("%d%s",&n,s+1);
56     Solve();
57 
58     return 0;
59 }
View Code

 

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

0,1互换着穿插,连续的 '(' 被分成了原来的 1/2;(tql)

AC代码:

Educational Codeforces Round 65 (Rated for Div. 2) D. Bicolored RBSEducational Codeforces Round 65 (Rated for Div. 2) D. Bicolored RBS
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define mem(a,b) memset(a,b,sizeof(a))
 5 const int maxn=5e5+50;
 6 
 7 int n;
 8 char s[maxn];
 9 int ans[maxn];
10 
11 void Solve()
12 {
13     int a=0;
14     int b=0;
15     for(int i=0;i < n;++i)
16     {
17         if(s[i] == '(')
18             ans[i]=a,a=!a;
19         else 
20             ans[i]=b,b=!b;
21         
22         printf("%d",ans[i]);
23     }
24     printf("\n");
25 }
26 int main()
27 {
28     scanf("%d",&n);
29     scanf("%s",s);
30     Solve();
31 
32     return 0;
33 }
View Code