链接：https://www.nowcoder.com/acm/contest/111/A
来源：牛客网
作为故事主角的托米是一名老师。
输入的第一行包含一个整数T，表示指定测试用例的数量。
每个测试用例前面都有一个空白行。
每个测试用例由一个合法括号序列组成。 每行只包含字符‘(‘和‘)‘。
对于每个测试用例，输出一行包含一个整数,表示相应几何表示的黑色部分的面积。
#define ll long long
const ll maxn = 4e5+5;
char s[maxn];
ll f[maxn];
ll ans = 0;
struct node
{
ll p, l;
node (ll _p=0, ll _l=0):p(_p), l(_l){}
};
stack<node>sta;
void fun(ll p1, ll p2){
ll num = 0;
for(ll i = p1; i <= p2; i++){
if (s[i] == ‘(‘) {
num++;
sta.push(node(i, 1));
}
else {
node v = sta.top();
sta.pop();
if (num%2 == 0) ans -= v.l*(i-v.p);
else ans += v.l*(i-v.p);
if (!sta.empty()){
node q = sta.top();
sta.pop();
q.l = max(q.l, v.l+1);
sta.push(q);
}
num--;
}
}
}
int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
ll t;
cin >> t;
while(t--){
scanf("%s", s+1);
ll len = strlen(s+1);
ll cnt = 0;
ans = 0;
for(ll i = 1; i <= len; i++){
if (s[i] == ‘(‘) cnt++;
else cnt--;
f[i] = cnt;
}
ll p = 1;
for(ll i = 1; i <= len; i++){
if (f[i] == 0){
fun(p, i);
//prllf("+++ %lld %lld\n", p, i);
p = i+1;
}
}
printf("%lld\n", ans);
}
return 0;
}
原文：https://www.cnblogs.com/ccut-ry/p/9124324.html