思路

我们注意到答案串一定是若干个可以变成一个可以做出 $k$ 个合法的括号序列的长度 $\le n$ 的序列再补上若干个 )。

显然，设答案串 $s$ 有 $k$ 对括号在最外层，那么合法子串个数为 $\frac{k(k+1)}{2}$。我们就可以构造了！

这样就可以在不浪费括号的情况下将答案串分成多个括号串。

设 $dp_i$ 为构造出 $i$ 个合法子串（即 $k$）所需的最小括号对数。

状态转移就是：$dp_i=dp_{i-\frac{j(j+1)}{2}}+j$。

我们先把这部分预处理出来。

如果 $2dp_k>n$ 则说明无解，否则在 dp 数组上递归构造（如果$dp_i=dp_{i-\frac{j(j+1)}{2}}+j$，那么就转移）。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,k,dp[100005];
void print(int x){
    if(!x) return;
    for(int i=1;i*(i+1)/2<=x;i++)if(dp[x-i*(i+1)/2]+i==dp[x])
        {for(int j=1;j<i;j++) cout<<"()";cout<<"(",print(x-i*(i+1)/2),cout<<")";return;}
}signed main(){
    cin>>T,memset(dp,0x3f,sizeof dp),dp[0]=0;
    for(int i=1;i<=100000;i++)
        for(int j=1;j*(j+1)/2<=i;j++) dp[i]=min(dp[i],dp[i-j*(j+1)/2]+j);
    while(T--){
        cin>>n>>k;if(dp[k]*2>n){cout<<"-1\n"; continue;}
        print(k);for(int i=dp[k]*2+1;i<=n;i++)cout<<")";cout<<'\n';
    }
}