题解：CF2143E Make Good

SUNCHAOYI · 2025-09-19 23:04:47 · 题解

简单构造题，但赛时被 D 卡了……

首先显然的是，n 为奇数肯定无解，直接特判。

接下来尝试构造出合法序列。一个重要的观察是，如果有两个相邻的相同括号，那么它们可以被同时移动到任意处。

:::info[Proof] 以两个相邻的左括号为例，只需要进行如下两次操作即可做一次平移：

:::

由于左右括号可以相互变化，因此只需要统计相邻的相同括号总数，设为 cnt 且默认均变为一种类型的括号。先把它们统一移到一侧，则剩下的括号只会有两种情况：

1. \texttt{()()} \cdots \texttt{()}

   将 cnt 个括号堆中的 \frac{cnt}{2} 个进行翻转即可。由于每次要翻转两个括号，所以 \frac{cnt}{2} 得是偶数，也就是 4 \mid cnt。构造变成 \texttt{()()} \cdots \texttt{()} \underbrace{\texttt{((} \cdots \texttt{(}}_{\frac{cnt}{2}\ 个} \underbrace{\texttt{))} \cdots \texttt{)}}_{\frac{cnt}{2}\ 个}。

2. \texttt{)()()} \cdots \texttt{()(}

   此时先要用 4 个括号把它变成 \texttt{(()()} \cdots \texttt{())}，然后剩余和 1 情况同理。

代码如下：

void solve ()
{
    int n = read (),cnt = 0,d = 0;scanf ("%s",str + 1);
    if (n & 1) {puts ("-1");return;}
    stack <char> s;
    for (int i = 1;i <= n;++i)
    {
        if (!s.empty () && s.top () == str[i]) cnt += 2,s.pop ();
        else s.push (str[i]);
    }
    vector <int> ans;
    while (!s.empty ()) ans.push_back (s.top ()),s.pop ();
    if (!ans.empty () && *(--ans.end ()) == ')') 
    {
        if (!cnt) {puts ("-1");return;}
        else cnt -= 2,ans.push_back ('('),ans.push_back ('('),++d;
    }
    reverse (ans.begin (),ans.end ());
    if (!ans.empty () && *(--ans.end ()) == '(') 
    {
        if (!cnt) {puts ("-1");return;}
        else cnt -= 2,ans.push_back (')'),ans.push_back (')'),--d;
    }
    if (d || (cnt & 3)) {puts ("-1");return;}
    for (auto v : ans) printf ("%c",v);
    for (int i = 1;i <= cnt / 2;++i) printf ("(");
    for (int i = 1;i <= cnt / 2;++i) printf (")");
    puts ("");
}