自动搬运

查看原文

来自洛谷，原作者为

	Rigel 苍山负雪，明烛天南。|| 高二现役 OIer。

搬运于2025-08-24 23:15:59，当前版本为作者最后更新于2025-05-11 20:22:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

若数 $n$ 为奇，无可解之法，此其显然者也。

若数 $n$ 为偶，则有构造之法曰：

首位必为 (，末位必为 )。

其间余空位 $n-2$ 处。

分之为二部，$[2,m]$ 置 )(，$[m+1,n-1]$ 置 ()。

其 $m$ 之值定法曰：

$m=\begin{cases}\dfrac{n}{2 }& \dfrac{n}{2} \equiv 1 \pmod{2}, \\ \\ \dfrac{n}{2} - 1 & \mathop{\operatorname{otherwise}}. \end{cases}$

今证此构造之法合法：

左部所置 )( 中，凡右括恒能与前者 )( 之左括相配，或与首左括相配；凡左括恒可与后者 )( 之右括相配，或与末右括相配。

右部所置 () 显然合法。

左部左括恒与右部左括相应，右部亦然。惟当 $\dfrac{n}{2} \equiv 0 \pmod{2}$ 时，中位二括必不可同。

是时，$f(S)$ 至大。

综上，此构造之法合法，又可极 $f(S)$ 之至大者也。

现代文版本

当 $n$ 为奇数时显然无解。

当 $n$ 为偶数时，我们有如下的构造方案：

首先位置 $1$ 一定是 (，位置 $n$ 一定是 )。

中间有 $n-2$ 个空位。

将其分成两半，$[2,m]$ 放置 )(，$[m+1,n-1]$ 放置 ()。

其中，$m=\begin{cases}\dfrac{n}{2 }& \dfrac{n}{2} \equiv 1 \pmod{2}, \\ \\ \dfrac{n}{2} - 1 & \mathop{\operatorname{otherwise}}. \end{cases}$

接下来证明这样构造的 $S$ 合法。

左半边放置的 )( 中，右括号总能与上一个放置的 )( 中的左括号匹配，或与第一个左括号匹配；左括号总能与下一个放置的 )( 中的右括号匹配，或与最后一个右括号匹配。

右半边放置的 () 显然合法。

左半边的左括号总能与右半边的左括号对应，右半边同理。除了当 $\dfrac{n}{2} \equiv 0 \pmod{2}$ 时，中间的两个括号不可能相同。

此时 $f(S)$ 最大。

综上，此构造方案合法，且可最大化 $f(S)$。

Code

#include<bits/stdc++.h>
#define int long long

using namespace std;

int T,n; 

inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
	return ret*f;
}

void _solve(){
	n=read();
	if(n&1){
		printf("-1\n");
		return;
	}
	printf("(");
	for(int i=1;i<=(n-2)>>1;i++){
		if(i<=(n-2)>>2)printf(")(");
		else printf("()");
	}
	printf(")\n");
}

signed main(){
	T=read();
	while(T--)_solve();
	return 0; 
}