CF1970A3题解

· · 题解

Part 1：前言

还挺有意思的一个题。

Part 2：正文

直接做没有太好的想法，因此考虑从题目所给的结论入手。

分析至此，我们已经有一个明确的解法了。对于 A2，我们可以分段后暴力模拟。对于 A3，我们发现，右括号不决定括号树的结构，只决定括号间的分段情况，因此我们直接以左括号为基本单位维护括号树结构，最后一遍 dfs 还原括号序列即可。

Part 3：代码

// To all the dreams made
// 在一切仍然可控之际
// The ones not too late
// 别让梦想从指尖溜走
// Just remember
// 你只需谨记
// It's okay to start again
// 重新振作，本不可耻

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

#define rep(i,l,r) for(int i(l);i<=(r);++i)
#define per(i,r,l) for(int i(r);i>=(l);--i)
#define eb emplace_back
#define File(filename) freopen(filename ".in","r",stdin),freopen(filename ".out","w",stdout)
#define Exit(p) fprintf(stderr,"[exit]: at breakpoint %d\n",p),exit(0);

#ifdef EXODUS
    #define Debug(...) fprintf(stderr,__VA_ARGS__)
#else
    #define Debug(...) 0
#endif

//=========================================================================================================
// Something about IO

template<typename T>
void read(T &x){
    x=0;T flg=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')flg=-1;ch=getchar();}
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    x*=flg;
}
template<typename T>
void seq_read(T bg,T ed){for(auto i=bg;i!=ed;++i)read(*i);}
template<typename T,typename... Args>
void read(T &x,Args &...args){read(x),read(args...);}

//=========================================================================================================
//Some useful function

template<typename T>
void cmax(T& x,T y){x=max(x,y);}
template<typename T,typename... Args>
void cmax(T& x,T y,Args ...args){cmax(x,y);cmax(x,args...);}
template<typename T>
void cmin(T& x,T y){x=min(x,y);}
template<typename T,typename... Args>
void cmin(T& x,T y,Args ...args){cmin(x,y);cmin(x,args...);}
template<typename T,typename U>
void seq_assign(T bg,T ed,U val){for(auto i=bg;i!=ed;++i)(*i)=val;}
template<typename T,class F,class=enable_if_t<is_invocable_v<F>>>
void seq_assign(T bg,T ed,F func){for(auto i=bg;i!=ed;++i)(*i)=func(i);}
template<typename T>
void seq_copy(T dstbg,T dsted,T srcbg,T srced){for(auto i=dstbg,j=srcbg;i!=dsted&&j!=srced;++i,++j)(*i)=(*j);}

//=========================================================================================================
// Define the global variables here.

bool membg=0;

constexpr int N=5e5+7;
int n,tot;
vector<int>g[N];
char s[N];
vector<int>seq;

bool memed=0;

//=========================================================================================================
// Code here.

void dfs(int u){
    seq.emplace_back(0);
    for(auto v:g[u]){
        dfs(v);
    }
    seq.emplace_back(1);
}

void solve(){
    scanf("%s",s+1);
    n=strlen(s+1);
    vector<int>pos;
    int j=1;
    while(j<=n){
        if(s[j]==')')
            break;
        pos.emplace_back(++tot);
        ++j;
    }
    ++j;
    int bound=tot;
    for(;j<=n;){
        vector<int>npos;
        auto it=pos.rbegin();
        while(it!=pos.rend()&&j<=n){
            if(s[j]==')')
                reverse(g[*it].begin(),g[*it].end()),++it,++j;
            else
                npos.emplace_back(++tot),g[*it].emplace_back(tot),++j;
        }
        reverse(npos.begin(),npos.end());
        swap(pos,npos);
    }
    for(int i=1;i<=bound;i++)
        dfs(i);
    for(int i=0;i<n;i++)
        putchar(seq[i]?')':'(');
    putchar('\n');
    return;
}

//=========================================================================================================

int main(){
    Debug("%.3lfMB\n",fabs(&memed-&membg)/1024.0/1024.0);
    int timbg=clock();
    int T=1;
    while(T--)solve();
    int timed=clock();
    Debug("%.3lfs\n",1.0*(timed-timbg)/CLOCKS_PER_SEC);
    fflush(stdout);
    return 0;
}