PAT A1093 Count PAT's

题目链接

解题思路

直接暴力会超时，所以分析题目发现，只需要找出每个A，然后将A左侧P的个数和A右侧T的个数相乘，然后求和取余即可。为了避免超时，使用空间换时间，定义一个int数组leftP来保存当前位置之前所有P的个数，然后再从后往前遍历字符串，定义一个变量rightT用来记录当前A右侧T的个数，如果遍历到A，就将rightT与当前位置的leftP相乘并求和取余，遍历完成就可得出结果！

代码

#include <cstdio>
#include <cstring>
const int maxn=1e5+10;
char seq[maxn];
int leftP[maxn];

int main(){
    scanf("%s",seq);
    int n=strlen(seq);
    leftP[0]=seq[0]=='P'?1:0;
    for(int i=1;i<n;i++){
        if (seq[i]=='P'){//将i位置之前的所有P的个数保存到数组leftP中
            leftP[i]=leftP[i-1]+1;
        }else{
            leftP[i]=leftP[i-1];
        }
    }
    int sum=0,rightT=0;
    for(int i=n-1;i>=0;i--){
        if (seq[i]=='T') rightT++;
        else if (seq[i]=='A'){
            sum=(sum+leftP[i]*rightT)%1000000007;
        }
    }
    printf("%d",sum);
    return 0;
}