【GDOI2018模拟9.17】永遠的三日天下

Description

給出一個字元串，求解一個括号序，使得每對比對的括号所在位置的字元都相等。

使答案字典序最小。

n<=4*1e6

Solution

了上克下行一這得使量力的邪正人鬼

棟棟搬的吼題

首先我們考慮先構造出一組可行解，這個顯然可以用單調棧來完成

如果我們把每個時刻單調棧裡面的東西想象成一個trie，那麼每一組配對x,y都滿足x-1和y在trie上所對應的節點相同。

考慮一個貪心，我們目前處理l,r這個區間，我們要給l比對

那麼肯定是比對最右邊一個合法的，即最大的pos滿足f[pos]=f[r]并且st[l]=st[pos]

這個可以用一個連結清單來存，每次把最大的選擇之後在連結清單上往前跳

但注意，我們的這個性質隻是一個充分條件，為了滿足必要性，我們要從後往前滿足這個東西

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=*+;
int n,id[][N],trie[N][],pre[N],cnt;
int stack[N],f[N],last[N],next[N],top;
char st[N],ans[N];
void add(int l,int r) {
    if (l<r) next[l]=last[r],last[r]=l;
}
void solve(int l,int r) {
    if (l>r) return;
    int now=st[l]-'a';
    int pos=id[now][f[r]];
    ans[l]='(';ans[pos]=')';
    add(pos+,r);
    add(l+,pos-);
}
int main() {
    freopen("seija.in","r",stdin);
    freopen("seija.out","w",stdout);
    scanf("%s",st+);n=strlen(st+);
    int x=;
    fo(i,,n) {
        int now=st[i]-'a';
        if (!top||st[stack[top]]!=st[i]) {
            stack[++top]=i;
            if (!trie[x][now]) trie[x][now]=++cnt;
            x=f[i]=trie[x][now];
        } else --top,x=f[i]=f[stack[top]];
        pre[i]=id[now][f[i]];
        id[now][f[i]]=i;
    }
    if (top) {
        puts("-1\n");
        return ;
    }
    add(,n);
    fd(i,n,) {
        while (last[i]) {
            int j=last[i];last[i]=next[j];
            solve(j,i);
        }
        id[st[i]-'a'][f[i]]=pre[i];
    }
    fo(i,,n) putchar(ans[i]);
    return ;
}