1.题目
https://pintia.cn/problem-sets/994805342720868352/problems/994805373582557184
找出诸如APPAPT中包含多少个PAT（注意不是指“连续”）。
2.思路
若直接暴力解会超时！！
可以先算出T的个数（一层for），然后再一次for从左至右统计P和T的个数，而在这层for循环内的最后，遇到A的时候就可以计算结果：因为遍历字符串的每个A，该A前面的P的个数和该A后面的T的个数的乘积即能构成的PAT的个数，在这个for遍历累加result即可。
3.代码
#include<cstdio> #include<stdlib.h> #include<algorithm> #include<string> #include<iostream> using namespace std; int main(){ string s; cin>>s; int len=s.length(),result=0,countp=0,countt=0; for(int i=0;i<len;i++){//此处灰常巧妙 if(s[i]=='T') countt++; } for(int i=0;i<len;i++){ if(s[i]=='P') countp++; if(s[i]=='T') countt--; if(s[i]=='A') result=(result+(countp*countt)%1000000007)%1000000007; } cout<<result; system("pause"); }
