Codeforces VK Cup 2015 A.And Yet Another Bracket Sequence（后缀数组+平衡树+字符串）

这题做得比较复杂。。应该有更好的做法

题目大意：

有一个括号序列，可以对其进行两种操作：

· 向里面加一个括号，可以在开头，在结尾，在两个括号之间加。

· 对当前括号序列进行循环移动，即把最后一个括号拿到开头来。

上述两种操作可以做任意次，要求添加最少的括号使得原序列变成一个合法括号序列。如果有多种可能，输出字典序最小的那一个。"(" < ")"。

题解：

首先计算左括号和右括号的数量，可以知道，不妨假设左括号的数量大于右括号

那么最少的方案就是在字符串右侧补充右括号，使得左括号的数量等于右括号的数量。

但是一个方案是否可行，要使得前面的每个前缀，都满足条件左括号的数量大于右括号

如果不满足，就循环移动即可，通过循环移动就一定会找到一个方案。

要输出字典序最小的方案，就需要后缀数组了

把字符串循环复制一遍，做后缀数组，那么就知道每个方案的排名

找最小且可行的方案输出即可。

另一种情况是左括号的数量小于右括号，也是同理的。

关于如何判断是否可行，这里是用的平衡树

写出每个位置的条件，每移动一次，对所有的条件影响都是相同的，所以用平衡树维护这些条件即可

#include <iostream>

#include <cstring>

#include <cstdio>

#include <vector>

#include <map>

#include <set>

using namespace std;

const int maxn = 2e6 + ;

int Wa[maxn], Wb[maxn], Wv[maxn], Ws[maxn], sa[maxn];

int Rank[maxn];

int height[maxn];

set<int> S;

map<int, int> M;

vector<int> V;

int a[maxn];

int cmp(int *r, int a, int b, int l)

{

    return r[a]==r[b] && r[a+l]==r[b+l];

}

void get_sa(int *r, int *sa, int n, int m)

{

    int i,j,p,*x=Wa,*y=Wb,*t;

    for(i=; i<m; i++) Ws[i]=;

    for(i=; i<n; i++) Ws[x[i]=r[i]]++;

    for(i=; i<m; i++) Ws[i]+=Ws[i-];

    for(i=n-; i>=; i--) sa[--Ws[x[i]]]=i;

    for(p=,j=; p<n; j*=,m=p)

    {

        for(p=,i=n-j; i<n; i++) y[p++]=i;

        for(i=; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;

        for(i=; i<n; i++) Wv[i]=x[y[i]];

        for(i=; i<m; i++) Ws[i]=;

        for(i=; i<n; i++) Ws[Wv[i]]++;

        for(i=; i<m; i++) Ws[i]+=Ws[i-];

        for(i=n-; i>=; i--) sa[--Ws[Wv[i]]]=y[i];

        for(t=x,x=y,y=t,p=,x[sa[]]=,i=; i<n; i++)

            x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;

    }

}

void get_height(int *r, int *sa, int n)

{

    int i, j, k=;

    for(i=; i<=n; i++) Rank[sa[i]]=i;

    for(i=; i<n; height[Rank[i++]]=k)

        for(k?k--:,j=sa[Rank[i]-]; r[i+k]==r[j+k]; k++);

}

void Hinsert(int x){

    if(M[x] == ) S.insert(x);

    M[x]++;

}

void Herase(int x){

    if(M[x] == ) S.erase(x);

    M[x]--;

}

char str[maxn];

int tr, tl;

int main()

{

    cin>>str;

    int n = strlen(str), nl = , nr = ;

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

        if(str[i] == '(') nl++, str[i] = ;

        else nr++, str[i] = ;

    }

    if(nl < nr){

        tl = ;

        for(int i = n-; i >= ; i--){

            if(str[i] == ) tl++;

            a[i] = *tl-(n-i);

            Hinsert(-a[i]);

        }

        tl = ;

        for(int i = n-; i >= ; i--){

            if(-(*S.begin()) <= -(n-i-)+*tl) V.push_back(i);

            Herase(-a[i]);

            if(str[i] == ) tl++;

            Hinsert(-(*nl-n-(n-i)+*tl));

        }

        int N = *n-;

        for(int i = ; i < n; i++) a[i] = str[i];

        for(int i = n; i < N; i++) a[i] = str[i-n];

        get_sa(a, sa, N+, );

        for(int i = ; i <= N; i++) Rank[sa[i]] = i;

        int maxr = N+, Kr = ;

        for(auto i : V){

            if(i+ >= N) break;

            if(Rank[i+] < maxr){

                maxr = Rank[i+];

                Kr = i+;

            }

        }

        a[N] = a[N-n];

        for(int i = ; i < nr-nl; i++) printf("(");

        for(int i = Kr; i < Kr+n; i++) printf("%c", a[i] ==  ? ')' : '(');

    } else {

        tr = ;

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

            if(str[i] == ) tr++;

            a[i] = *tr-i-;

            Hinsert(-a[i]);

        }

        tr = ;

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

            if(-(*S.begin()) <= -i+*tr) V.push_back(i);

            Herase(-a[i]);

            if(str[i] == ) tr++;

            Hinsert(-(*nr-n-i-+*tr));

        }

        int N = *n-;

        for(int i = ; i < n; i++) a[i] = str[i];

        for(int i = n; i < N; i++) a[i] = str[i-n];

        get_sa(a, sa, N+, );

        for(int i = ; i <= N; i++) Rank[sa[i]] = i;

        int maxr = N+, Kr = ;

        for(auto i : V){

            if(Rank[i] < maxr){

                maxr = Rank[i];

                Kr = i;

            }

        }

        for(int i = Kr; i < Kr+n; i++) printf("%c", a[i] ==  ? ')' : '(');

        for(int i = ; i < nl-nr; i++) printf(")");

    }

}

巴特西

Codeforces VK Cup 2015 A.And Yet Another Bracket Sequence（后缀数组+平衡树+字符串）

最新文章

热门文章