个人练习-PAT甲级-1093 Count PAT‘s_综合

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805373582557184

康复训练做题。
题意：找出给出的字符串中PAT的数量，只要求P在A前，A在T前。
想了想肯定是要用O(N)的算法做的，不然铁定超时，即扫描一遍就做出来。
思路是从后往前扫描字符串

如果是T就记录当前T的数量（numT++）
如果是A，可以开始凑组合AT了，记录当前AT组合的数量（numAT++）
如果是P，恭喜，可以开始计算【由这个P组成的】PAT个数了，实际上就是让总数加上当前AT组合的数量

完整代码

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<map>
#include<set>
#include<queue>
#include<string.h>using namespace std;const int C = 1000000007;int main() {
    string str;cin >> str;int ret = 0, numT = 0, numAT = 0;vector<int> rem(str.size(), 0);for (int i = str.size() - 1; i >= 0; i--) {
    if (str[i] == 'T') {
    numT++;}else if (str[i] == 'A') {
    numAT += numT;}else if (str[i] == 'P') {
    ret += numAT;ret %= C;}}printf("%d", ret);return 0;
}