深夜切題——PAT (Basic Level)-1040

1040. 有幾個PAT（25）

時間限制 120 ms

記憶體限制 65536 kB

代碼長度限制 8000 B

判題程式 Standard 作者 CAO, Peng

字元串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
      

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const long long int mod=1000000007;
char s[100000];
int main()
{
    gets(s);
    long long int cp=0,answer=0,len=strlen(s);
    for(int i=0;i<len;++i){
        if(s[i]=='P')++cp;
        if(s[i]=='A'&&cp){
            long long int ct=0;
            for(int j=i+1;j<len;++j){
                if(s[j]=='T')++ct;
            }
            answer=(answer+cp*ct)%mod;
        }
    }
    cout<<answer<<endl;
    return 0;
}
           

以A為中心計算，一開始總是重複掃後面的T導緻逾時

是以先掃記錄下PAT個數，犧牲空間換取時間。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const long long int mod=1000000007;
char s[100000];
int main()
{
    gets(s);
    long long int cp=0,cc=0,np=0,nc=0,answer=0,len=strlen(s);
    for(int i=0;i<len;++i){
        if(s[i]=='P')++cp;
        else if(s[i]=='A')++cc;
    }
    for(int i=0;i<len;++i){
        if(s[i]=='P')++np;
        if(s[i]=='A'){
            answer=(answer+np*((len-cp-cc)-(i-np-nc)))%mod;
            ++nc;
        }
    }
    cout<<answer<<endl;
    return 0;
}