PAT B1040/A1093題解---解決記憶體超限測試點的問題

1040 有幾個PAT （25 分）

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

現給定字元串，問一共可以形成多少個 PAT？

輸入格式：

輸入隻有一行，包含一個字元串，長度不超過10

​5

​​ ，隻包含 P、A、T 三種字母。

輸出格式：

在一行中輸出給定字元串中包含多少個 PAT。由于結果可能比較大，隻輸出對 1000000007 取餘數的結果。

輸入樣例：

APPAPT

輸出樣例：

2

思路：直接暴力統計的話，因為120ms限制容易逾時，是以采用分解優化的方法，來降低時間複雜度。即按兩輪循環來統計每一位左邊的P數量和右邊的T數量，然後最後一輪循環來計算能夠構成多少個PAT。

#include <iostream>
#include <cstdio>
#include <cstring>
const int MAXN = 100010;
const int MOD = 1000000007;
int main() {
    char str[MAXN];
    scanf("%s", str);
    int len = strlen(str);
    int leftP[MAXN] = {0};
    // 計算左邊的P的數量
    for(int i = 0; i < len; i++) {
        if(i > 0) {
            leftP[i] = leftP[i-1];
        }
        if(str[i] == 'P') {
            leftP[i]++;
        }
    }
    // 計算右邊的T的數量
    int rightT[MAXN] = {0};
    for(int i = len - 1; i >= 0; i--) {
        if(i < len-1) {
            rightT[i] = rightT[i+1];
        }
        if(str[i] == 'T') {
            rightT[i]++;
        }
    }

    int ans = 0;
    for(int i = 0; i < len; i++) {
        if(str[i] == 'A') {
            ans = (ans + leftP[i] * rightT[i]) % MOD;
        }
    }

    printf("%d", ans);
    return 0;
}
           

同時也貼出參考的兩位大神的代碼，有同工之妙，也有獨到之處

//AC1
#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    cin >> s;
    int len = s.length(), result = 0, countp = 0, countt = 0;
    for (int i = 0; i < len; i++) {
        if (s[i] == 'T')
            countt++;
    }
    for (int i = 0; i < len; i++) {
        if (s[i] == 'P') countp++;
        if (s[i] == 'T') countt--;
        if (s[i] == 'A') result = (result + (countp * countt) % 1000000007) % 1000000007;
    }
    cout << result;
    return 0;
}
//AC2
#include <iostream>
#include <cstdio>
#include <cstring>

const int MAXN = 100010;
const int MOD = 1000000007;

int main() {
    char str[MAXN];
    scanf("%s", str);

    int len = strlen(str);

    int p = 0, pa = 0, pat = 0;
    for(int i = 0; i < len; i++) {
        if(str[i] == 'P') {
            p++;
        } else if(str[i] == 'A') {
            pa = (pa + p) % MOD;
        } else {
            pat = (pat + pa) % MOD;
        }
    }

    printf("%d", pat);
    return 0;
}