1040 有幾個PAT (25 分)
- 2019 年 10 月 8 日
- 筆記
1040 有幾個PAT (25 分)
字符串 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
【我的代碼】
// 1040 有幾個PAT (25 分).cpp : 此文件包含 "main" 函數。程序執行將在此處開始並結束。 // #include <iostream> #include <string> using namespace std; int main() { //輸入 string a; cin >> a; int i = 0; long num_T = 0, num_AT = 0, num_PAT = 0; //計算 for (i = a.size() - 1; i >= 0; i--) { if (a[i] == 'T') { num_T++; } else if (a[i] == 'A') {//找到一個A後，就能和前面所有數過的數進行組合，組成PAT num_AT = (num_AT + num_T) % 1000000007; } else {//對P而言，只能結合前面所有AT的數量，並不能與T直接掛鈎 num_PAT = (num_PAT + num_AT) % 1000000007; } } cout << num_PAT % 1000000007; return 0; }
【思路】
通過讀題，我們發現對於由同一個T結尾PAT可以允許存在多個。也就是說，PAT的個數取決於P的個數和後面AT的個數（同一個AT可以對應多個P從而形成PAT），而AT的個數又取決於T的個數（同一個T可以跟多個A組合成AT）。因此我們僅需從後往前計數即可。
