Codeforces Round #603 (Div. 2) E. Editor

E. Editor

题目链接：

https://codeforces.com/contest/1263/problem/E

题目大意：

输入一个字符串S1含有‘（’ ， ‘）’ ， ‘R’ ， ‘L’ 以及其他字符。根据这个字符串，得到相应的字符串S2。起始idx=1即S2的初始坐标，然后从左到右读取S1，当遇到'L'，idx减小1（当无法左移的情况下idx不减小），当遇到'R'，idx增加1，当读取到其他字符时，将idx这个位置上的字符更新为读取到的新的字符。然后输出每一步得到的字符串S2最大的括号级数（例：（（）（））为2，（（（）））为3），如果不是一个左右括号完全匹配的字符串输出-1。

解题思路：

另（为1，）为-1，其他字符为0，构造一个线段树，维护区间和与前缀最小值、前缀最大值。可以知道，当前缀最小值小于0时代表不是一个括号完全匹配的字符串，当区间和不为0也表示这不是一个括号完全匹配的字符串。

代码：

 #include <bits/stdc++.h>

 using namespace std;

 const int N = 4e6;

 string s;

 int ans[N];

 int mi[N],ma[N];

 void update(int node,int start,int end,int p,int v){

     if(start==end){

         ans[node]=v;

         ma[node]=v;

         mi[node]=v;

         return ;

     }

     int mid=(start+end)>>;

     int left_node=*node+;

     int right_node=*node+;

     if(p<=mid){

         update(left_node,start,mid,p,v);

     }

     else{

         update(right_node,mid+,end,p,v);

     }

     ans[node]=ans[left_node]+ans[right_node];

     ma[node]=max(ma[left_node],ans[left_node]+ma[right_node]);// 一个区间前缀最大值是左边区间中的最大值，与右边区间最大值加上左边区间和中的最大值

     mi[node]=min(mi[left_node],ans[left_node]+mi[right_node]);// 一个区间前缀最小值是左边区间中的最小值，与右边区间最小值加上左边区间和中的最小值

 }

 int main(){

     int n,idx=;

     cin>>n>>s;

     for(int i=;i<n;i++){

         if(s[i]=='L'){

             if(idx>)    idx--;

         }

         else if(s[i]=='R'){

             idx++;

         }

         else if(s[i]=='('){

             update(,,n,idx,);//更新此位置改为1

         }

         else if(s[i]==')'){

             update(,,n,idx,-);//更新此位置改为-1

         }

         else{

             update(,,n,idx,);//更新此位置改为0

         }

         if(mi[]>=&&ans[]==){//判断输出

             cout<<ma[]<<" ";

         }

         else{

             printf("-1 ");

         }

     }

     cout<<endl;

     return ;

 }

巴特西

Codeforces Round #603 (Div. 2) E. Editor

E. Editor

最新文章

热门文章