题解 | #小红的括号串#

题目链接

小红的括号串

题目描述

给定四种括号字符串的数量： $a$ 个 "(("， $b$ 个 "))"， $c$ 个 "()"，以及 $d$ 个 ")("。判断是否能将这些字符串全部拼接起来，形成一个合法的括号序列。

一个合法的括号序列是指可以通过插入 1 和 + 形成一个正确的算术表达式的序列。

思路分析

一个字符串是合法的括号序列，必须满足两个经典条件：

字符串中左括号 ( 的总数必须等于右括号 ) 的总数。
对于字符串的任意一个前缀，其中左括号的数量必须大于或等于右括号的数量。

我们可以根据这两个条件来推导能否成功构造。

1. 总数相等条件

首先，我们计算手头所有括号块提供的 ( 和 ) 的总数。

左括号 ( 总数 = $2 \cdot a + 1 \cdot c + 1 \cdot d$
右括号 ) 总数 = $2 \cdot b + 1 \cdot c + 1 \cdot d$

为了让二者相等，必须满足 $2 \cdot a = 2 \cdot b$ ，化简后得到 $a = b$ 。这是一个必要条件。如果 "((" 的数量不等于 "))" 的数量，无论如何拼接，最终的 ( 和 ) 总数都不可能相等，因此无法构成合法序列。

2. 前缀合法条件

现在我们假设 $a = b$ 成立。我们需要找到一种拼接顺序，使得在任何位置，已拼接的 ( 数量都不少于 ) 数量。

我们可以把 ( 看作使计数器加一，) 看作减一。计数器必须始终保持非负。

"(("：最安全的块，它能稳定地增加计数器。
"()"：也是安全的，它对计数器的最终值没有影响，且过程中不会使计数器降低到初始值以下。
")(" 和 "))"：是“危险”的块，因为它们以 ) 开头，会立即降低计数器。要拼接它们，必须确保拼接前的计数器有足够的余量。

关键在于能否处理 ")(" 这种块。要拼接一个 ")("，要求拼接前的计数器至少为 $1$ 。而唯一能稳定提供计数器增量的块是 "(("。

考虑一个关键场景：如果我们没有任何 "((" 块，即 $a = 0$ 。

根据第一个条件，这也意味着 $b = 0$ 。我们手上只剩下 "()" 和 ")("。
任何合法的非空序列都必须以 ( 开头，所以我们只能先拼接 "()" 块。
拼接任意数量的 "()" 块后，计数器都会回到 $0$ 。
此时，如果我们还有 ")(" 块没用（即 $d > 0$ ），拼接它就会立刻让计数器变为 $-1$ ，导致序列不合法。
因此，我们得出一个重要推论：如果 $a=0$ ，那么 $d$ 必须也为 $0$ 。

反之，如果 $a > 0$ ，我们总可以通过先拼接所有 "((" 块来获得一个大于 $0$ 的计数器，这个正数“余量”足以让我们安全地拼接所有 ")(" 和 "()" 块，最后用等量的 "))" 块将计数器清零。

最终结论

一个合法的序列能够被构造出来，当且仅当满足以下两个条件：

$a = b$
如果 $a=0$ ，则 $d=0$ 。

这两个条件可以合并为一个逻辑表达式： a == b AND (a > 0 OR d == 0)。（特殊情况：若所有数都为0，空字符串是合法的，此逻辑也正确处理）。

代码

cpp
java
python

#include <iostream>

using namespace std;

void solve() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    
    // a: "(("
    // b: "))"
    // c: "()"
    // d: ")("

    // 只要 a=b，并且没有“a=0 但 d>0”的捣乱情况，就可以。
    // a>0 保证了可以处理 d，d=0 保证了不需要处理 d。
    if (a == b && (a > 0 || d == 0)) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    private static void solve(Scanner sc) {
        long a = sc.nextLong(); // "(("
        long b = sc.nextLong(); // "))"
        long c = sc.nextLong(); // "()"
        long d = sc.nextLong(); // ")("

        // 条件1: a 和 b 必须相等
        // 条件2: 如果 a 为 0，则 d 必须为 0
        if (a == b && (a > 0 || d == 0)) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

import sys

def solve():
    a, b, c, d = map(int, sys.stdin.readline().split())
    # a: "(("
    # b: "))"
    # c: "()"
    # d: ")("

    # 条件1: a 和 b 必须相等
    # 条件2: 如果 a 为 0，则 d 必须为 0
    if a == b and (a > 0 or d == 0):
        print("YES")
    else:
        print("NO")

def main():
    try:
        t_str = sys.stdin.readline()
        if not t_str:
            return
        t = int(t_str)
        for _ in range(t):
            solve()
    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

算法及复杂度

算法：逻辑判断
时间复杂度：对于每组测试数据，仅需进行几次整数比较和逻辑运算，因此时间复杂度为 $O(1)$ 。
空间复杂度： $O(1)$ 。