简单构造题，但赛时被 D 卡了……
首先显然的是，$n$ 为奇数肯定无解，直接特判。
接下来尝试构造出合法序列。一个重要的观察是，如果有两个相邻的相同括号，那么它们可以被同时移动到任意处。
$\textbf{Proof}$
以两个相邻的左括号为例，只需要进行如下两次操作即可做一次平移：
由于左右括号可以相互变化，因此只需要统计相邻的相同括号总数，设为 $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$ 情况同理。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| 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 ("");
}
|
