题解：CF2143E Make Good

· · 题解

题目：洛谷 || CF

怎么是简单题啊/崇拜

题目分析

考虑两种操作可以让我们干什么：

我们先将所有 )) 替换为 ((。这样就可以得到 ..()(...()(... 这样的东西。

考虑一个 )，假设它右边是 ((，那么我们可以把它右移两位（)(( \to ))) \to (()）。

考虑两个 ) 会发生什么。比如说 )(()，这时我们可以把中间两个翻转一下，变成 ))))，然后再把左边两个和右边两个翻转，变成 ((((。

所以我们得到：

于是我们维护哪些位置的 ) 是不能变的。可以用一个栈维护，如果栈顶与当前之间的括号个数为偶数，那么就都弹出，否则加入。

然后开始构造。由于要构造括号序列，就贪心地将 ) 往后放。不妨先把所有 ) 移到左边，这时右边都是 ...(((( 的形式，从右往左翻转直到总右括号数量为 n/2 为止。

为什么要假定把 ) 移到左边：比如 (()(((，直接是不能把 ( 右移成 (((()(，这样会非常难解决；但如果我们先把它转化成 )((((( 这样就可以贪心在右边填 ))。

然后再把所有左边的 ) 尽可能移到右边就行了。

最后可能还要再判下是否合法。根据实现决定吧。

Code

自认为实现比较高妙（）

// by wangyizhi(571247)
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//bool Mst;
using namespace std;
namespace wyzfastio{}
using namespace wyzfastio;
using ll=long long;
using ld=long double;
//#define int ll
using pii=pair<int,int>;
const int N=2e5+5;
int a[N];
//bool Med;
signed main()
{
//  cerr<<"Memory Size: "<<abs((&Med)-(&Mst))/1024.0/1024<<" MB\n";
//  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//  freopen("in.in","r",stdin);
//  freopen("out.out","w",stdout);
    int t;read(t);
    while(t--) [&]()->void
    {
        int n;string s;
        read(n,s);
        for(int i=0;i<=n+1;i++) a[i]=0;
        stack<int> stk;
        for(int i=0;i<n;i++) if(s[i]==')')
        {
            if(stk.size()&&(i-stk.top())&1) stk.pop();
            else stk.push(i);
        }
        for(int i=n,j=1;j<=(n/2-(int)stk.size())/2*2;i--,j++) a[i]=1;
        for(int lst=n-(n/2-(int)stk.size())+1;stk.size();)
        {
            if((lst^stk.top())&1) {if(lst>2)a[lst-=2]=1;}
            else {if(lst>1)a[lst-=1]=1;}
            stk.pop();
        }
        int p=0;
        for(int i=1;i<=n;i++) if((p+=a[i]?-1:1)<0) return write("-1\n"),void();
        if(p) return write("-1\n"),void();
        for(int i=1;i<=n;i++) write(a[i]?')':'(');
        write('\n');
    }();
    return 0;
}