立志用更少的代碼做更高效的表達

---

PAT乙級最優(yōu)題解——>傳送門

---

字符串 APPAPT 中包含了兩個單詞 PAT，其中第一個 PAT 是第 2 位§，第 4 位(A)，第 6 位(T)；第二個 PAT 是第 3 位§，第 4 位(A)，第 6 位(T)。

現(xiàn)給定字符串，問一共可以形成多少個 PAT？

輸入格式：
輸入只有一行，包含一個字符串，長度不超過10^5，只包含 P、A、T 三種字母。

輸出格式：
在一行中輸出給定字符串中包含多少個 PAT。由于結果可能比較大，只輸出對 1000000007 取余數(shù)的結果。

輸入樣例：
APPAPT
輸出樣例：
2

---

解題思路

本題的核心思路在于如何利用記憶數(shù)組提高效率。

在我們計算的過程中， 會出現(xiàn)很多次重復計算， 因此考慮將子結果存放在數(shù)組中， 需要時直接查看即可。 這就是記憶數(shù)組。(動態(tài)規(guī)劃思想)

解題步驟：

順序遍歷P的個數(shù)并記錄。 逆序遍歷T的個數(shù)并記錄。

最后遍歷A的個數(shù)， 每遍歷到一個A字符， 就將其前P字符個數(shù)與其后的T字符個數(shù)相乘， 累加，求余。 最后輸出即可。

注意： 盡量使用getline輸入string字符串，用cin輸入偶爾會報錯（僅限于PTA平臺）。

---

代碼展示

#include<bits/stdc++.h> using namespace std; int b[100010], c[100010]; int main() {string s; getline(cin, s);int Pnum[s.length()] = {0};for(int i = 1; i < s.length(); i++) {Pnum[i] = Pnum[i-1];if(s[i-1] == 'P') ++Pnum[i];} int tnum = 0, sumPAT = 0; //tnum表示該字符右側字符T的數(shù)量for(int i = s.length()-1; i >= 0; i--) {if(s[i] == 'T') ++tnum;else if(s[i] == 'A') sumPAT = (sumPAT + Pnum[i]*tnum)%1000000007;}cout << sumPAT;return 0; }

---

每日一句

當你想要“尊崇內心而活”，你就會發(fā)現(xiàn)，自己不會被外在多余的事情所困擾

總結

以上是生活随笔為你收集整理的1040 有几个PAT (25分)——18行代码AC的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。