深夜切题——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;
}