题解：CF2143E Make Good

Welcome24ever · 2025-09-19 14:52:50 · 题解

首先非常显然，当 n 为奇数的时候无解。奇数的时候根本构造不出来合法的括号序列。

遇到这种，操作无限次的题目，一个非常常见且好用的切入点是，观察操作中的不变量。

那么在这个题里什么是没有改变的呢？我们观察这个操作的本质，我们每次操作都是改变了一个 i 和对应的 i+1，我们拆成奇数位和偶数位来看，观察奇数位的左括号数量和偶数位的左括号数量。

我们发现每次翻转，都会使得奇数位和偶数位同时多一个或少一个左括号。也就是说在这个题中，操作的不变量是奇数位和偶数位左括号数量的差值，我们记一个字符串 s 偶数下标和奇数下标的左括号差值为 \text{cnt}(s)。因此两个字符串 s 和 t，只要满足 \text{cnt}(s) = \text{cnt}(t)，s 和 t 之间就一定可以互相转化。

下一步我们需要分析，什么样的字符串才是可构造的。首先对于一个合法的括号序列来说，第一个位置必须是左括号，最后一个位置一定是右括号。我们记 \displaystyle m = \frac{n}{2}。那么在偶数位置，一定至少有一个左括号。而在奇数位置，因为最后一个括号必须是右括号，也就是最多有 m-1 个左括号。

因此对于一个合法的 \text{cnt}(t)，其必定满足 \text{cnt}(t) \geq 1 - (m-1)=2-m，这是合法的下界。我们再考虑一下合法的上界，最大的时候就是字符串是若干个 () 组成的，这时候 \text{cnt}(t) 可以取到上界 m。

同时还存在一个约束，就是 \text{cnt}(t) 必须满足和 m 奇偶性相同。这个也好理解，一次操作不会改变左括号数的奇偶性，不会改变 \text{cnt}，所以总左括号的奇偶性和 \text{cnt} 的奇偶性是绑定的。合法的字符串左括号数量是 m，如果 \text{cnt} \equiv m \pmod 2 不成立，就无法让左括号数量抵达 m 的奇偶性，自然无法抵达 m。

因此我们能构造出合法串的条件是：

2 - m\leq \text{cnt}(s) \leq m \land \text{cnt}(s) \equiv m (\bmod 2)

接下来我们只需要考虑最后的答案如何构造就好了，我们考虑构造一个形如这样的最终答案：

t = \underbrace{( \cdots (}_{k\ \text{个}} \;\; \underbrace{() \cdots ()}_{\,m-k\ \text{对}} \;\; \underbrace{) \cdots )}_{k\ \text{个}}

形如这样的字符串肯定是合法的，问题是 k 是多少，我们可以对着上面这个算出来：

当 k 为偶数，\text{cnt}(t) = m - k。
当 k 为奇数，\text{cnt}(t) = k - m + 1。

于是当我们知道了 \text{cnt}(s) 的具体值，因为 \text{cnt}(t) = \text{cnt}(s) 我们可以求解 k：

当 \text{cnt}(t)\geq 0，取偶数 k = m - \text{cnt}(t)。
当 cnt(t) < 0，取奇数 k = \text{cnt}(t) + m -1。

有了 k，我们可以按照上面的形式在 O(n) 的时间复杂度内构造出答案。

//   再次鼓起丧失的勇气。
#include<bits/stdc++.h>

using namespace std;
const int Welcome24ever = 0;
#define endl '\n'
#define int long long
typedef pair<int, int> PII;

void IHaveNoLimitation() {
    int n;
    string str;
    cin >> n >> str;
    if (n & 1) {
        cout << -1 << endl;
        return;
    }
    int m = n / 2;
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (str[i] == '(') {
            if (i & 1) cnt--;
            else cnt++;
        }
    }
    if (cnt < 2 - m || cnt > m || ((cnt - m) & 1)) {
        cout << -1 << endl;
        return;
    }
    int tmp;
    if (cnt >= 0) tmp = m - cnt;
    else tmp = cnt + m - 1;
    string ans;
    for (int i = 0; i < tmp; i++) ans += '(';
    for (int i = 0; i < m - tmp; ++i) ans += "()";
    for (int i = 0; i < tmp; i++) ans += ')';
    cout << ans << endl;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        IHaveNoLimitation();
    }
    return Welcome24ever;
}