1093 Count PAT's （25 分)

2019-04-14

1093 Count PAT’s （25 分)

The string APPAPT contains two PAT‘s as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the second one is formed by the 3rd, the 4th, and the 6th characters.

Now given any string, you are supposed to tell the number of PAT‘s contained in the string.

Input Specification:

Each input file contains one test case. For each case, there is only one line giving a string of no more than 105 characters containing only P, A, or T.

Output Specification:

For each test case, print in one line the number of PAT‘s contained in the string. Since the result may be a huge number, you only have to output the result moded by 1000000007.

Sample Input:

APPAPT

Sample Output:

作者: CAO, Peng

单位: Google

时间限制: 150 ms

内存限制: 64 MB

代码长度限制: 16 KB

题目大意

统计字符串中PAT的数量

分析

不能算难，但比较有意思。必须用o(n)的算法，否则超时。pc记录P的个数，pa记录PA出现个数，res记录结果。遍历字符串，出现P则让pc++，出现A则之前所有P与当前A能组成PA，pa+=pc。出现T则之前所有PA与当前T可组成PAT。res+=pa。

代码

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
#include <sstream>

using namespace std;
string s;
long int res;
int pc, pa;

int main() {
    cin >> s;
    int l = s.length();
    for (int i = 0; i < l; i++) {
        if (s[i] == 'P')
            pc++;
        if (s[i] == 'A')
            pa += pc;
        if (s[i] == 'T')
            res += pa;
    }
    cout << res % 1000000007;
    return 0;
}