Parentheses Matching加强版[HDU6799][2020多校3][思维题]

题目

HDU

题目大意：
给你一个字符串 $s$，仅包含 $(,?,)$ ，可以将 $?$ 替换为 $($，$)$
$Q1:$ 问构成长度最小的字典序最小的字符串？
$Q2:$ 问构成字典序最小的字符串？

*()()*
Q1ans:()()
Q2ans:(()())**()()
Q1ans:()()
Q2ans:()()

思路

鸣谢 $LW$
可以先解决原题
我们肯定优先放 $($
我们记录一个前缀和，如果小于 $0$ 就考虑在最左边的 $?$ 放 $($

• 一个括号序列合法当且仅当前缀和不小于 $0$ 且最后等于 $0$

然后我们再从右往左类似填 $)$
最后如果仍然不合法就真的有问题
现在保证了字典序最小，并且左括号尽量靠左，右括号尽量靠右
然后我们只用尝试不断两端往内加 $(............)$ 比较字典序即可
暴力是 $O(n^2)$ 的
然后我们仔细思考一下我们添加一对括号会怎样影响字典序

原来是
$(..................)$
如果是这样我们的字典序一定变小
$((....................))$
但是如果这样
$()(....................)$
就不一定了
发现影响我们答案
但此时再往内加 ${}^{\prime }({)}^{\prime }$ 也一定不优
发现此时影响我们的始终是当前最靠左的右括号记为 $p$
$.(..(...(..).............$
如果我们添加的一对 $()$ 的 $)$ 在 $p$ 的右侧，那么一定添加
否则我们由于不一定新添加的 $)$ 的右边都固定了，直接比较后缀字典序
此时肯定 $?$ 都为 $)$ 预处理 $Hash+$ 二分即可

代码

#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<climits>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define ULL unsigned long long
int read(){
    int x=0;char c=getchar();while(c<'0'||'9'<c) c=getchar();while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();return x;
}
#define MAXN 200000
char s[MAXN+5],t[MAXN+5];
ULL pw[MAXN+5],p,Hash[MAXN+5];
int n,pre[MAXN+5],nxt[MAXN+5],stk[MAXN+5];
void Init(){
    int L=1,R=n;while(L<R){
    while(L<R&&s[L]!='*') t[L]=s[L],L++;while(L<R&&s[R]!='*') t[R]=s[R],R--;t[L++]='(',t[R--]=')';}t[n+1]=Hash[n+1]=0;for(int i=n;i>=R;i--){
    if(t[i]=='(') Hash[i]=Hash[i+1]*p+1;else Hash[i]=Hash[i+1]*p+2;}return ;
}
ULL GetHash(int L,int R){
    return Hash[L]-Hash[R+1]*pw[R-L+1];}
bool check(int A,int B){
    int L=0,R=n-B+2;while(L+1<R){
    int Mid=(L+R)>>1;if(GetHash(A,A+Mid-1)==GetHash(B,B+Mid-1))L=Mid;else R=Mid;}return t[A+L]<t[B+L];
}
int main(){
    freopen("bracket.in","r",stdin);freopen("bracket.out","w",stdout);p=31;pw[0]=1;for(int i=1;i<=MAXN;i++)pw[i]=pw[i-1]*p;int T=read();while(T--){
    scanf("%s",s+1);n=strlen(s+1);for(int i=1,lst=0;i<=n+1;s[i]=='*'?lst=i:lst=lst,i++)pre[i]=lst;for(int i=n,lst=n+1;i>=0;s[i]=='*'?lst=i:lst=lst,i--)nxt[i]=lst;int L=nxt[0],R=pre[n+1],sum=0,tp=0;for(int i=1;i<=n;i++){
    if(s[i]!='*')sum+=s[i]=='('?1:-1;if(sum<0){
    if(L>i){
    puts("NoAnswer!");goto Break;}s[L]='(',L=nxt[L],sum++;}}while(sum){
    if(R<L){
    puts("NoAnswer!");goto Break;}s[R]=')',R=pre[R],sum--;}for(int i=1;i<=n;i++){
    if(s[i]!='*')sum+=s[i]=='('?1:-1;if(sum<0){
    puts("NoAnswer!");goto Break;}}if(sum){
    puts("NoAnswer!");continue;}Init();L=1,R=n;while(L<R&&s[L]!='*') L++;while(L<R&&s[R]!='*') R--;for(int i=1;i<=n;i++){
    if(s[i]==')'){
    int cntL=0,ansL=tp,pos=i,tmpl=L,tmpr=R;while(L<i&&L<R){
    while(R<stk[tp]) tp--;cntL++;if(tp+cntL>ansL||(tp+cntL==ansL&&check(R,pos))){
    pos=min(R,pos);for(int j=tmpl;j<=L;j++)if(s[j]=='*') s[j]='(';for(int j=R;j<=tmpr;j++)if(s[j]=='*') s[j]=')';tmpl=L,tmpr=R;ansL=tp+cntL;}L++,R--;while(L<R&&s[L]!='*') L++;while(L<R&&s[R]!='*') R--;}tp=0;}else if(s[i]=='(') stk[++tp]=i;}for(int i=1;i<=n;i++)if(s[i]!='*')putchar(s[i]);puts("");Break:;}return 0;
}