CF847C Sum of Nestings 题解

Code_Fish_Hp / 2023-08-18 / 原文

题目链接

思路

一道简单的递归题，题目要求我们构建一个有 \(n\) 对括号且有 \(k\) 对嵌套的括号序列（一对嵌套表示的是两对对应的括号一个被另一个包含）。如果无法构建满足条件的括号序列，则输出 Impossible。

确定上限：当 \(k \leq \frac {n \times n - 1}{2}\) 时才有解。

对于 ((((…))))((((…)))) 的括号序列，只要将里面某的一对 \(\binom{}{}\) 向外边提出 \(i\) 对 \(\binom{}{}\) 即可使得嵌套的数量减少 \(i\)。那么这样就可证明可以构造出的答案范围是稠密的。

综上，直接使用递归函数即可 AC。

参考代码（请勿抄袭）:

#include<bits/stdc++.h> //万能头
#define ll long long //把ll定为long long，节约打字时间
using namespace std;
ll n,k;

void Nes(ll n,ll k){//构造函数
    if(n==0) return; //当所有的括号都输出完，代表任务完成，退出函数
    if(k>=n-1){
        putchar('(');
        Nes(n-1,k-(n-1));//递归
        putchar(')');
    }
    else{
        putchar('(');
		putchar(')');
        Nes(n-1,k);
    }
    /*putchar函数可以让程序输出一个字符，putchar(')') 等价于 cout<<')' */
}

int main(){
    scanf("%lld %lld",&n,&k);
    if(n*(n-1)/2<k) printf("Impossible\n");//不可能完成的任务
    else Nes(n,k);//开始构造
    return 0;
}