【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;  }