原题链接：https://pintia.cn/problem-sets/994805260223102976/problems/994805282389999616
字符串 APPAPT 中包含了两个单词 PAT。其中第一个 PAT 是第2位（P） ，第4位（A），第6位（T）；第二个 PAT 是第3位（P），第4位（A），第6位（T）。 现给定字符串，问一共可以形成多少个 PAT？
输入格式： 输入只有一行，包含一个字符串，长度不超过10^5，只包含 P、A、T 三种字母。
输出格式： 在一行中输出给定字符串中包含多少个 PAT。由于结果可能比较大，只输出对 1000000007 取余数的结果。
输入样例： APPAPT 输出样例： 2
思路：此题有点难度。首先要读懂题意，拼成PAT三个字符的规则是：对于每一个A，取它之前的任一个P和它之后的任一个T，三者即可拼成满足题意的PAT，所以关键因素就是字符T的个数。故先求出T的个数，之后遍历字符串，对于P，记录其个数，对于每个A，求出pat的组合之和，而对于T，则num_t–。
本题AC代码：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll flag = 1e9+7; //取模基数 const int maxn = 1e5+10; char str[maxn]; int main() { while(scanf("%s",str)==1) { int num_p = 0,num_a = 0,num_t = 0; int i=0,j=0; int ret = 0; int len = strlen(str); for(i=0;i<len;++i) { if(str[i]=='T') //先求出T的个数 num_t++; } for(j=0;j<len;j++) { if(str[j] == 'P') { num_p++; } else if(str[j] == 'T') { num_t--; } else if(str[j] == 'A') {//对于每个A，求pat的组合数 ret = (ret+num_p*num_t)%flag; } } printf("%d\n",ret); memset(str,0,sizeof(str)); } return 0; }