括号

思路

• 因为要求构造的字符串长度不超过100000。所以我们可以把拆成的形式。可以先预处理,然后进行拆分。拆分好后就可以很容易的进行构造。

• ps：注意因为时构造非空的括号字符串，所以当时需要进行特判

代码

// Problem: 括号
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/9981/B
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=100010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

ll f[N];
vector<int> g;

void solve(){
    int k;cin>>k;
    if(!k) {
        cout<<")(";
        return;
    }
    while(k){
        int p=upper_bound(f+1,f+100000,k)-f-1;
        g.pb(f[p]);
        k-=f[p];
    }
    int pre=0;
    for(int x:g){
        int i,j;
        for(i=sqrt(x);i>=1;i--){
            if(x%i==0){
                j=x/i;
                break;
            }
        }
        if(i>j) swap(i,j);
        rep(t,1,pre-j) cout<<")";
        rep(t,1,i) cout<<"(";
        pre=j;
    }
    rep(t,1,pre) cout<<")";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    for(ll i=1;i<=100000;i++) f[i]=i*i;
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}