【PAT乙级】有几个PAT

• 2019 年 11 月 8 日
• 筆記

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/weixin_42449444/article/details/84865691

题目描述：

字符串APPAPT中包含了两个单词“PAT”，其中第一个PAT是第2位(P),第4位(A),第6位(T)；第二个PAT是第3位(P),第4位(A),第6位(T)。现给定字符串，问一共可以形成多少个PAT？

输入描述:

输入只有一行，包含一个字符串，长度不超过105，只包含P，A，T三种字母。

输出描述：

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

输入样例：

APPAPT

输出样例：

2

解题思路：

首先，这个题看完之后有点懵逼，然后仔细分析得出这三点：①每个P对应的PAT组合数量是A之前P的数量;②每个A对应的PAT组合数量是T之前所有甲对应的PA组合数量的累加;③所有的PAT组合数量是所有T对应的PAT组合数量的累加。

AC代码：

#include <bits/stdc++.h>  using namespace std;    int main()  {      string s;      cin >> s;      int len = s.length();      int countp = 0, countpa = 0, countpat = 0;      for (auto it : s)      {          if(it == 'P')          {              countp++;          }          else if(it == 'A')          {              countpa += countp;          }          else if(it == 'T')          {              countpat += countpa;              countpat %= 1000000007;          }      }      cout << countpat<< endl;      return 0;  }