Skip to content

CF2143E Make Good

原题链接：E. Make Good

Tag：构造

题目描述

给定一个长度为 \(n\) 的括号串 \(s\)。你可以任意次数（包括零次），以任意顺序执行以下操作：

  • 选择一个下标 \(1 \leq i < |s|\)，如果 \(s_i = s_{i+1} = \texttt{(}\)，则将这两个字符都替换为 \(\texttt{)}\)。
  • 选择一个下标 \(1 \leq i < |s|\)，如果 \(s_i = s_{i+1} = \texttt{)}\)，则将这两个字符都替换为 \(\texttt{(}\)。

请找到一个合法括号序列 \(t\)，它可以通过对 \(s\) 执行上述操作得到；如果不存在这样的 \(t\)，则输出 \(-1\)。

数据说明：

每个测试包含多组测试用例。第一行包含一个整数 \(t\)（\(1 \le t \le 10^4\)），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 \(n\)（\(1 \le n \le 2 \cdot 10^5\)），表示字符串的长度。

第二行包含一个长度为 \(n\) 的字符串 \(s\)，只由字符 \texttt{(} 和 \texttt{)} 组成。

保证所有测试用例中 \(n\) 的总和不超过 \(2 \cdot 10^5\)。

分析

首先非常显然，当 \(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\)，我们直接按照上面那个形式构造就可以了。

代码实现

//   再次鼓起丧失的勇气。
#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;
}

日志

本页面创建于 2024/9/19 02:08