529A And Yet Another Bracket Sequence

传送门

题目大意

给定有一个长度为n

n的括号序列，现在有两种操作：

在任意一个位置插入有一个左括号或右括号
将末尾的一个括号放到最前面

可以对这个序列进行若干次操作，问在使括号序列合法的前提下，长度最短是多少，如果有多组解，输出字典序最小的

分析

首先最后的长度一定等于（原字符串长度+左括号与右括号数量的差值），现在我们考虑让其的字典序尽量的小

我们预处理前缀和，’(‘为+1，’)'为-1

我们可以发现，最终的答案一定是从序列中的某一位开始循环n

n次，最后补上需要补足的括号数的，然后我们就只需要查找长度为n

n的子串中合法且最小的那串

判断合法的过程可以用hash+二分

二分的是两个字符串第一个不一样的地方

实际还有后缀数组做法，然后先咕了

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

#define uli long long

const uli hsh = ;

const uli hsh2 = ;

const uli mod = 1e9+;

const uli mod2 = ;

int n,m;

string s,t;

char c[];

uli pw[],h[],pw2[],h2[];

int sum[],pre[],sur[],le,ri;

inline pair<uli,uli> v(int l,int r){

    return make_pair((h[r]-(l?h[l-]:)*pw[r-l+]%mod+mod)%mod,

             (h2[r]-(l?h2[l-]:)*pw2[r-l+]%mod2+mod2)%mod2);

}

inline bool ck(int i,int j){

    int l=,r=m;

    while(r-l>){

      int mid=(l+r)>>;

      if(i+mid->=m||j+mid->=m||v(i,i+mid-)!=v(j,j+mid-))r=mid;

        else l=mid;

    }

    if(i+r->=m||j+r->=m)return ;

    return t[i+r-]<t[j+r-];

}

int main(){

    int i,j,k;

    scanf("%s",c);

    s=c;

    t=s+s;

    n=s.length();

    m=t.length();

    pw[]=;

    for(i=;i<=m;i++)pw[i]=pw[i-]*hsh%mod;

    h[]=t[];

    for(i=;i<m;i++)h[i]=(h[i-]*hsh+t[i])%mod;

    pw2[]=;

    for(i=;i<=m;i++)pw2[i]=pw2[i-]*hsh2%mod2;

    h2[]=t[];

    for(i=;i<m;i++)h2[i]=(h2[i-]*hsh2+t[i])%mod2;

    for(i=;i<n;i++)sum[i]=(i?sum[i-]:)+(s[i]=='('?:-);

    pre[]=sum[],sur[n-]=sum[n-];

    for(i=;i<n;i++)pre[i]=min(sum[i],pre[i-]);

    for(i=n-;i>=;i--)sur[i]=min(sum[i],sur[i+]);

    int maxl=1e9+,pl=-;

    if(sum[n-]<)le=-sum[n-];

      else ri=sum[n-];

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

      k=(i?sum[i-]:);

      int w=min(sur[i]-k,sum[n-]-k+(i?pre[i-]:));//重点!!!

      int ll=max(-w,max(,-sum[n-]));

      if(ll+ri+n<maxl){

          maxl=ll+ri+n;

          le=ll;

          pl=i;

      }else if(ll+ri+n==maxl&&ck(i,pl)){

          pl=i;

      }

    }

    for(i=;i<=le;i++)cout<<"(";

    for(i=pl;i<n;i++)cout<<s[i];

    for(i=;i<pl;i++)cout<<s[i];

    for(i=;i<=ri;i++)cout<<")";

    return ;

}

巴特西

529A And Yet Another Bracket Sequence

最新文章

热门文章