Educational Codeforces Round 65 (Rated for Div. 2) D. Bicolored RBS
链接:https://codeforces.com/contest/1167/problem/D
题意:
A string is called bracket sequence if it does not contain any characters other than "(" and ")". A bracket sequence is called regular (shortly, RBS) if it is possible to obtain correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, "", "(())" and "()()" are RBS and ")(" and "(()" are not.
We can see that each opening bracket in RBS is paired with some closing bracket, and, using this fact, we can define nesting depth of the RBS as maximum number of bracket pairs, such that the 22-nd pair lies inside the 11-st one, the 33-rd one — inside the 22-nd one and so on. For example, nesting depth of "" is 00, "()()()" is 11 and "()((())())" is 33.
Now, you are given RBS ss of even length nn. You should color each bracket of ss into one of two colors: red or blue. Bracket sequence rr, consisting only of red brackets, should be RBS, and bracket sequence, consisting only of blue brackets bb, should be RBS. Any of them can be empty. You are not allowed to reorder characters in ss, rr or bb. No brackets can be left uncolored.
Among all possible variants you should choose one that minimizes maximum of rr's and bb's nesting depth. If there are multiple solutions you can print any of them.
思路:
双指针往后跑就行了,每次变一个颜色。
代码:
#include <bits/stdc++.h>
using namespace std; const int MAXN = 2e5+10;
int res[MAXN]; int main()
{
int n;
string s;
cin >> n >> s;
int color = 0;
int l = 0, r = 0;
while (s[r] != ')')
r++;
int cnt = 0;
while (cnt < n)
{
res[l++] = color;
res[r++] = color;
cnt += 2;
while (l < n && s[l] != '(')
l++;
while (r < n && s[r] != ')')
r++;
color ^= 1;
}
for (int i = 0;i < n;i++)
cout << res[i];
cout << endl; return 0;
}
最新文章
- 获取文件hash值
- eclipse中搭建svn开发管理环境
- js原型基础
- 转:js清空数组
- Local Optimization Revisited
- 建立Clojure开发环境-使用IDEA和Leiningen
- HDU ACM 1007 Quoit Design 分而治之的方法,最近点
- linux centos下安装g++
- html css基础(一)
- C语言之函数
- Mac下安装FFmpeg教程
- 将Excel表中的数据导入到数据库
- Spring_boot入门(1)
- mysql8.0 定时创建分区表记录 每天定时创建下一天的分区表
- C# 判断文件编码
- Median String CodeForces - 1144E
- Node.js npm uuid
- 它是对 ACME(automated certificate management environment) 协议的实现,只要实现了 ACME 协议的客户端都可以跟它交互。
- python网络编程-多进程multiprocessing
- 如何实现监听 console.log