题解：CF2143E Make Good

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

首先显然的是，

n

为奇数肯定无解，直接特判。

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

Proof

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

\texttt{(()} \to \texttt{)))} \to \texttt{)((}

由于左右括号可以相互变化，因此只需要统计相邻的相同括号总数，设为

cnt

且默认均变为一种类型的括号。先把它们统一移到一侧，则剩下的括号只会有两种情况：

$\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}\ 个}$ 。
$\texttt{)()()} \cdots \texttt{()(}$

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

代码如下：

CPP

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 ("");
}

题解：CF2143E Make Good

文章操作

相关推荐

评论

题解：CF2143E Make Good