关于算法-数据结构:PAT甲级1093-Count-PATs

题目粗心：

给定一个只蕴含 P,A,T 的字符串，让其计算有多少个 PAT 组合

算法思路：

对一个确定地位的 A 来说，以它造成的 PAT 的个数等于它右边 P 的些个数乘以它左边 T 的个数。例如对字符申 APPAPT 的两头那个 A 来说，它右边有两个 P，左边有一个 T，因而这个 A 能造成的 PAT 的个数就是 2 ×1=2. 于是问题就转换为: 对字符串中的每个 A, 计算它右边 P 的个数与它左边 T 的个数的乘积，而后把所有 A 的这个乘积相加，最初的后果就是该字符串中所有的 PAT 组合数目。那么当初就是须要获取每一个地位的右边的 P 和左边的 T 的数，在这里咱们应用 leftP 和rightP别离保留以后地位右边的 P 和左边的 T 的个数。之所以能够这样保留，是因为以后地位 i 右边的 P 的个数和 i - 1 地位右边 P 的个数具备继承性，要么相等，要么相差 1。那么这样咱们能够先遍历一遍所有的字符串中所有的 T 呈现的个数，而后应用 ans 保留所有的 PAT 组合数目，再次遍历字符串的过程中，如果以后字符为 P 那么就让 leftP 加 1，如果为 T，就让 rightT 减一，如果为 A，就累计leftP*rightT。

留神点：

1、测试点 3 和 4 考查取模，不能在最初统计实现后再取模，须要每计算一次就取模。

提交后果：

AC 代码：

#include <cstdio>
#include <string>
#include <iostream>

using namespace std;

int main(){
    string s;
    cin>>s;
    int len = s.size();
    int leftP = 0;
    int rightT = 0;
    int ans = 0;// 记录 PAT 的个数
    for (int i = 0; i < len; ++i) {if(s[i]=='T'){++rightT;}
    }
    for (int j = 0; j < len; ++j) {if(s[j]=='P'){++leftP;} else if(s[j]=='T'){--rightT;} else if(s[j]=='A'){
            ans += leftP*rightT;
            ans %= 1000000007;
        }
    }
    cout<<ans;
    return 0;
}