Codeforces 1906L Palindromic Parentheses

考虑先判定有无解对应的 \(k\) 的范围。

首先若 \(k = n\) 一定无解，因为字符串开头是 \(\texttt{(}\) 结尾是 \(\texttt{)}\) 匹配不上。
下界因为各有 \(\frac{n}{2}\) 个 \(\texttt{()}\)，所以可以先猜测下界就为 \(\frac{n}{2}\)。

考虑构造到这个下界。
能发现只需要形如 \(\texttt{(((...)))}\) 即可。

然后考虑增量法往上一个一个增加。
发现 \(\texttt{()(((...)))}\) 会使左边的小括号组的右括号与右边的大括号组的右括号匹配上，即匹配长度会增加 \(2\)，且此时左边小括号组的左括号是未匹配的。
继续增加，\(\texttt{()(((...)))()}\)，能发现最左边的左括号与右边的括号组的左括号匹配上了，\(+2\)，且此时右括号组的右括号是未匹配的。
于是能发现再在左边加上 \(\texttt{()}\) 又能 \(+2\)，然后又是右边加，左边加这样的。

放的数量可以考虑解方程，设最中间各有 \(x\) 个 \(\texttt{(}\) 和 \(\texttt{)}\)，左右侧共有 \(y\) 个 \(\texttt{()}\)，有方程 \(\begin{cases}2x + 2y = n\\ x + 2y = k\end{cases}\)，解得 \(\begin{cases}x = n - k \\ y = k - \frac{n}{2}\end{cases}\)。
于是就可以中间放上 \(n - k\) 个 \(\texttt{(}\) 和 \(\texttt{)}\)，然后依次在左边和右边来回放共 \(k - \frac{n}{2}\) 个 \(\texttt{()}\)。

#include<bits/stdc++.h>
int main() {
    int n, k; scanf("%d%d", &n, &k);
    int x = n - k, y = k - n / 2;
    if (x <= 0 || y < 0) return puts("-1"), 0;
    for (int i = 1; i <= (y + 1) / 2; i++) printf("()");
    for (int i = 1; i <= x; i++) printf("(");
    for (int i = 1; i <= x; i++) printf(")");
    for (int i = 1; i <= y / 2; i++) printf("()"); 
    return 0;
}