P12497 回文括号序列

Rigel · 2025-05-11 20:22:05 · 题解

思路

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

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

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

其间余空位 n-2 处。

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

其 m 之值定法曰：

今证此构造之法合法：

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

右部所置 () 显然合法。

左部左括恒与右部左括相应，右部亦然。惟当 \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; 
}