2503: Find the Cow!

时间限制: 1.000 Sec  内存限制: 64 MB
提交状态

题目描述

Bessie the cow has escaped and is hiding on a ridge covered with tall grass.  Farmer John, in an attempt to recapture Bessie, has decided to crawl through the grass on his hands and knees so he can approach undetected.  Unfortunately, he is having trouble spotting Bessie from this vantage point. The grass in front of Farmer John looks like a string of N (1 <= N <= 50,000) parentheses; for example:
)((()())())

Farmer John knows that Bessie's hind legs look just like an adjacent pair of left parentheses ((, and that her front legs look exactly like a pair of adjacent right parentheses )).  Bessie's location can therefore be described by a pair of indices x < y such that (( is found at position x, and )) is found at position y.  Please compute the number of different such possible locations at which Bessie might be standing.

输入

* Line 1: A string of parentheses of length N (1 <= N <= 50,000).

输出

* Line 1: The number of possible positions at which Bessie can be  standing -- that is, the number of distinct pairs of indices   x < y at which there is the pattern (( at index x and the   pattern )) at index y.

样例输入 Copy

)((()())())

样例输出 Copy

4

提示

There are 4 possible locations for Bessie, indicated below:
1. )((()())())
    ^^   ^^
2. )((()())())
     ^^  ^^
3. )((()())())
     ^^     ^^
4. )((()())())
    ^^      ^^

思路：

某奆佬原话：
区间计数的话一般都是枚举一个端点算另一个端点的套路
比如说这里是要找((...))匹配对吧
对于一个((的位置
所有位置大于他的))串都可以产生一个贡献
假设我们现在枚举((的位置
那对于每一个((我只要知道它右边有多少个))就可以了对吧
那么只要维护一个))的数量
从n到1枚举((的位置
遇到))就加入计数
遇到((就把计数加入答案
这样

（太强了qaq）
代码：

#include <iostream>
#include <cstring>
using namespace std;
int main ()
{char str[50005];scanf("%s",&str[1]);int num=0;int res=0;int len=strlen(&str[1]);for(int i=len;i>=2;i--){if(str[i]==')'&&str[i-1]==')'){num++;}if(str[i]=='('&&str[i-1]=='('){res+=num;}}printf("%d\n",res);return 0;
}