PAT乙级 1040 有几个PAT (25分)

1040 有几个PAT (25分)

字符串 APPAPT 中包含了两个单词 PAT，其中第一个 PAT 是第 2 位§，第 4 位(A)，第 6 位(T)；第二个 PAT 是第 3 位§，第 4 位(A)，第 6 位(T)。

现给定字符串，问一共可以形成多少个 PAT？

输入格式：

输入只有一行，包含一个字符串，长度不超过10​⁵​​ ，只包含 P、A、T 三种字母。

输出格式：

在一行中输出给定字符串中包含多少个 PAT。由于结果可能比较大，只输出对 1000000007 取余数的结果。

输入样例：

APPAPT

输出样例：

2

思路：

两种思路：
1.统计每个A左边有多少P，右边有多少T，然后用乘法原理。
2.统计每个T左边有多少个AP,然后用乘法原理。

统计数据：

题解 方法一：

#include <cstdio>
#include <cstring>
using namespace std;

char inpt[110000];
long long tmpa=0,nump=0,numt=0;

int main(){
    scanf("%s",inpt);
    for(int i=0;i<strlen(inpt);i++) //统计T的数量
        inpt[i]=='T'?numt++:1;
    for(int i=0;i<strlen(inpt);i++){  //如果找到P，p加一，如果找到T，t减一。如果找到A，结果加上p*t
        inpt[i]=='P'?nump++:1;
        inpt[i]=='A'?tmpa = (tmpa+nump*numt)%1000000007:1;
        inpt[i]=='T'?numt--:1;
    }
    printf("%lld",tmpa);
    return 0;
}

题解 方法二：

#include <cstdio>
using namespace std;

char ip[100100];
int summ,p,ap,t,i;

int main(){
    for(scanf("%s",ip);ip[i];++i){
        ip[i]=='P'? p += 1 : 0;    //p代表当前p的数量
        ip[i]=='A'? ap += p : 0;   //ap代表当前ap的数量
        ip[i]=='T'? summ = (summ + ap) % 1000000007 : 0;  //如果找到T,summ就加上ap的数量
    }
    printf("%d",summ);
    return 0;
}

题解 方法三：

#include <cstdio>
using namespace std;

char str1[110000];
int p,t,a,all;

int main(){
    scanf("%s",str1);
    for(int i=0;str1[i];str1[i++]=='T'?t++:1); //统计T的数量
    for(int i=0;str1[i];str1[i++]=='T'?t--:1)  //如果找到P，p加一，如果找到T，t减一。如果找到A，结果加上p*t
        str1[i]=='P'?p++:str1[i]=='A'?all=(all+(p*t))%1000000007:1;
    printf("%d",all);
    return 0;
}