SDUT 2017 Autumn Single Contest G
链接
Recall that the bracket sequence is considered regular if it is possible to insert symbols ‘+’ and ‘1’ into it so that the result is a correct arithmetic expression. For example, a sequence “(()())” is regular, because we can get correct arithmetic expression insering symbols ‘+’ and ‘1’: “((1+1)+(1+1))”. Also the following sequences are regular: “()()()”, “(())” and “()”. The following sequences are not regular bracket sequences: “)(“, “(()” and “())(()”.

In this problem you are given two integers n and k. Your task is to construct a regular bracket sequence consisting of round brackets with length 2·n with total sum of nesting of all opening brackets equals to exactly k. The nesting of a single opening bracket equals to the number of pairs of brackets in which current opening bracket is embedded.

For example, in the sequence “()(())” the nesting of first opening bracket equals to 0, the nesting of the second opening bracket equals to 0 and the nesting of the third opening bracket equal to 1. So the total sum of nestings equals to 1.

Input
The first line contains two integers n and k (1 ≤ n ≤ 3·105, 0 ≤ k ≤ 1018) — the number of opening brackets and needed total nesting.

Output
Print the required regular bracket sequence consisting of round brackets.

If there is no solution print “Impossible” (without quotes).

Example
Input
3 1
Output
()(())
Input
4 6
Output
(((())))
Input
2 5
Output
Impossible
Note
The first example is examined in the statement.

In the second example the answer is “(((())))”. The nesting of the first opening bracket is 0, the nesting of the second is 1, the nesting of the third is 2, the nesting of fourth is 3. So the total sum of nestings equals to 0 + 1 + 2 + 3 = 6.

In the third it is impossible to construct a regular bracket sequence, because the maximum possible total sum of nestings for two opening brackets equals to 1. This total sum of nestings is obtained for the sequence “(())”.

翻译：回想一下，如果可以向其中插入符号“+”和“1”以使得结果是正确的算术表达式，则括号序列被认为是规则的。例如，序列“（（）（））”是规则的，因为我们可以得到正确的算术表达式，符号“+”和“1”：“（（1 + 1）+（1 + 1））”。此外，以下序列是常规的：“（）（）（）”，“（（））”和“（）”。以下序列不是常规括号序列：“）（”，“（（）”and“（））（（）”。

在这个问题中，你给了两个整数n和k。你的任务是构造一个正方括号序列，它由长度为2·n的圆括号组成，所有开口括号的嵌套总和等于k。单个开放支架的嵌套等于嵌入当前开放支架的一对支架的数量。

例如，按照（（）（（））的顺序，第一个括号的嵌套等于0，第二个括号的嵌套等于0，第三个括号的嵌套等于1.因此，总和嵌套等于1。

输入
第一行包含两个整数n和k（1≤n≤3.105，0≤k≤1018） - 开口括号和所需的总嵌套数。

产量
打印由圆括号组成的必需的常规括号序列。

如果没有解决方案打印“不可能”（不含引号）。

例
输入
3 1
产量
（）（（））
输入
4 6
产量
（（（（））））
输入
2 5
产量
不可能
注意
声明中检查了第一个例子。

在第二个例子中，答案是“（（（（））））”。第一个括号的嵌套为0，第二个嵌套为1，第三个嵌套为2，第四个嵌套为3，所以嵌套总和等于0 + 1 + 2 + 3 = 6 。

在第三种情况下，不可能构造正则括号序列，因为两个开口括号的嵌套的最大可能总和等于1.这个嵌套总和是针对序列“（（））”获得的。

题意：给定 n 与 k，代表括号的数目与嵌套之和，输出一种嵌套序列满足这种情况。

括号的数量是自然数和，一开始以为可能会有很多种组合，后来一想，最多只可能是两种组合，先找出来小于最后结果的最大数，然后

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
struct node
{
    int l,r;
}b[2000];
long long ss[300000];
int main()
{
    for(int i=1;i<=300000;i++)
    {
            ss[i]=ss[i-1]+(i-1);
          //cout<<ss[i]<<endl;
    }
    //预处理自然数前n项和
    //其实用（i-1)*i/2就可以计算出来

  int n;
  long long k;
    cin>>n>>k;
    if(ss[n]<k)
           printf("Impossible\n");
    else if(ss[n]==k)
    {
        for(int i=1;i<=n;i++)
        {
            printf("(");
        }
        for(int i=1;i<=n;i++)
        {
            printf(")");
        }
    }
    else
    {
        int y = 0,i;
        for(i=n;i>=0;i--)
        {
            if(ss[i]<=k)
            {
                k-=ss[i];
                n-=i;
                break;
            }

        }
        for(int j=1;j<=i;j++)
        {
            printf("(");
        }
        cout<<")";
        for(int j=i-1;j>=1;j--)
        {
            if(k==j)
          //补全剩下的，因为括号权值是连续的，
          //所以肯定能满足，复制程序，打印两组示例， 5 8，5 9
    //即可明白
            {
               printf("()");
               n--;
            }
            printf(")");
        }
        for(int j=1;j<=n;j++)
        printf("()");
// 因为只有一对计数为0，所以这里用于清理多余的
    }

    return 0;
}

法2：
dfs，暂不理解

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))

void c(ll n,ll k)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    if(n==0)return ;
    if(k>=n-1)
    {
        cout<<'(';
        c(n-1,k-(n-1));
        cout<<')';
    }
    else 
    {
        cout<<"()";
        c(n-1,k);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,k;
    cin>>n>>k;
    if(n*(n-1)/2<k)cout<<"Impossible";
    else c(n,k);
    cout<<endl;
    return 0;
}