Party Monster 的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求判断能否通过至多一次移除子串并任意重排其字符，得到正则括号序列。
核心解法：只需检查左括号数量是否等于右括号数量。

分析

核心观察

操作允许移除整个字符串，因此可以将所有字符重新排列成任意顺序。只要左右括号数量相等，就能构造出正则括号序列。

思路

正则括号序列的必要条件是左括号数等于右括号数。
若两者相等，选择整个字符串作为子串移除，再按任意顺序重新插入所有字符，例如先插入所有左括号再插入所有右括号，得到 (((...)))，这是合法的正则序列。
若两者不等，则任何括号序列都不可能正则，因此答案为 NO。

具体示例

样例 )( 中左括号 $1$ ~1~ 个，右括号 $1$ ~1~ 个，相等，输出 YES；
样例 ((( 中左括号 $3$ ~3~ 个，右括号 $0$ ~0~ 个，不等，输出 NO。

算法步骤

读入测试用例数 t。
对每个测试用例，读入长度 n 和字符串 s。
统计 s 中左括号 '(' 的数量。
若该数量等于 n - 该数量（即右括号数相同），输出 "YES"；否则输出 "NO"。

复杂度分析

时间复杂度： $O(n)$ ~O(n)~，其中 $n$ ~n~ 为字符串长度，所有测试用例总长度不超过 $2 \times 10^5$ ~2 \times 10^5~。
空间复杂度： $O(1)$ ~O(1)~。

实现注意事项

若 $n$ ~n~ 为奇数，左右括号数量不可能相等，可直接输出 NO。
统计左括号数量使用整型变量即可。
输出大小写不敏感，统一使用大写。

源代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;
        int open = 0;
        for (char c : s) {
            if (c == '(') open++;
        }
        if (open * 2 == n) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    t = int(data[0])
    idx = 1
    out = []
    for _ in range(t):
        n = int(data[idx])
        s = data[idx + 1]
        idx += 2
        open_cnt = s.count('(')
        if open_cnt * 2 == n:
            out.append("YES")
        else:
            out.append("NO")
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

目前没有评论。