PAT甲级1093.

目录

A1093

题目

样例

输入:

APPAPT

输出:

2

思路和坑点

　　计算字符串中的PAT个数。使用数学中的排列组合知识，对于一个序列来说，如果PPPPPPATTTTTTTT，类似的字符串中，对于每一个A来说，若左边有np个P，右边有nt个T，则从左侧挑出一个P有np种可能，右侧挑出一个T有nt种可能，则它可以组成np*nt个“PAT”。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int cntP=0,cntT=0,ans=0;                //分别统计T和P的个数 
    string pat;
    getline(cin,pat);
    for(int i=0;i<pat.size();i++)           //统计T的个数 
        if(pat[i]=='T') cntT++;
    for(int i=0;i<pat.size();i++){          //遍历字符串 
        if(pat[i]=='P') cntP++;             //统计当前位置之前P的个数 
        else if(pat[i]=='T') cntT--;        //计算当前位置之后T的个数 
        else {
            ans+=cntT*cntP;                 //如果当前位置为A，根据排列组合的知识，组成的PAT个数为：A左侧的P的个数*A右侧的T的个数 
            ans%=mod;                       //每次计算过后取模 
        }
    }
    cout<<ans;
    return 0;
}