C. Bracket Sequences Concatenation Problem

题目链接

Educational Codeforces Round 45 (Rated for Div. 2)--C. Bracket Sequences Concatenation Problem

题解

中档题。题意大概是给定n串由"("、")"组成的字符串,将它们两两相加,求能完成匹配的字符串数量。
将读入的字符串分为三类,一类是自身能完成匹配,与其配对的必定也是自身能完成匹配的字符串。第二类是左括号数量大于右括号数量,第三类是右括号数量大于左括号数量。第二类必定与第三类括号数量之查相同的串匹配。统计好每类的数量相乘相加即为所求答案。注意,int范围在这题当中不够使用。

代码

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#define LL long long
using namespace std;
LL n, ll, rr, temp;
string s;
LL l[300005];
LL r[300005];
LL mid;
bool boo;
int main() {
    cin >> n;
    for (int q = 1; q <= n; q++) {
        cin >> s;
        ll = rr =temp= 0;
        boo = true;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(')ll++;
            else if (s[i] == ')')rr++;
        }
        if (ll == rr) {
            for (int i = 0; i < s.size(); i++) {
                if (s[i] == '(')temp++;
                else if (s[i] == ')')temp--;
                if (temp < 0) {
                    boo = false; break;
                }
            }
            if (boo)mid++;
        }
        else if (ll > rr) {
            for (int i = 0; i < s.size(); i++) {
                if (s[i] == '(')temp++;
                else if (s[i] == ')')temp--;
                if (temp < 0) {
                    boo = false; break;
                }
            }
            if (boo)l[ll - rr]++;
        }
        else if (rr > ll) {
            for (int i = s.size()-1; i >= 0; i--) {
                if (s[i] == ')')temp++;
                else if (s[i] == '(')temp--;
                if (temp < 0) {
                    boo = false; break;
                }
            }
            if (boo)r[rr - ll]++;
        }
    }
    LL ans = 0;
    for (int i = 1; i <= 300000; i++) {
        ans += l[i] * r[i];
    }
    ans += mid * mid;
    cout << ans;    
}

标签: implementation

添加新评论