cf990c Bracket Sequences Concatenation Problem

OI 思维
文章目录

这是一道普及组难度题……然而我脑子瓦特了……

就是分成四类:

  • 好序列
  • 需要若干左括号的序列
  • 需要若干右括号的序列
  • 凉透了的废材序列

拼一拼就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <string>
#include <map>
using namespace std;
int n, cnt[5];
map<int,int> mp;
string a;
void isLegal(string a){
int din=0, len=a.length(), notSaveAble=0;
for(int i=0; i<len; i++){
if(a[i]=='('){
if(din<0){
notSaveAble += -din;
din = 0;
}
din++;
}
else
din--;
}
if(din<0){
notSaveAble += -din;
din = 0;
}
if(!notSaveAble && !din) mp[0]++;
else if(!notSaveAble && din) mp[din]++;
else if(notSaveAble && !din) mp[-notSaveAble]++;
}
int main(){
cin>>n;
while(n--){
cin>>a;
isLegal(a);
}
long long ans=0;
for(int i=0; i<=300000; i++)
ans += (long long)mp[i] * mp[-i];
cout<<ans<<endl;
return 0;
}