B1040 有几个PAT (25分)

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

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

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

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

输入样例： APPAPT 输出样例： 2

思路：

统计A前P的个数，A后T的个数，（P的个数*T的个数）就是这个A可以组成的PAT,然后再往后找A，不断的把符合题意的加入到sum中

注：

先把所有的T找到，方便遍历的时候从前往后找的时候方便，如果在A前就出现了T，就再把这个组不成PAT的T去除掉 #include<stdio.h> #include<iostream> #include<string> using namespace std; int main() { string s; cin>>s; int p=0,t=0,sum=0;//p为P的个数，t为T的个数，sum为最终可以组成PAT的个数 int n=s.length() ; for(int i=0;i<n;i++) { if(s[i]=='T') t++;//遍历整个数组，统计T的个数 } for(int i=0;i<n;i++) { if(s[i]=='P') p++; if(s[i]=='T') t--;//在A之前就有T，这时候构不成PAT，就把这个T从t的总数中减去 if(s[i]=='A') sum=(sum+(p*t)%1000000007)%1000000007; }//A的左边P的个数已经统计，A的右边T的个数也知道啦，相乘p*t就可以知道这个A可以构成几个PAT printf("%d",sum); return 0; }

为什么要对1000000007取模（取余）？？？让我的柳女神跟你讲，点击即可